fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int MOD = 1e9 + 7;
  7. const int MAX = 200005;
  8.  
  9. int fact[MAX];
  10. int invFact[MAX];
  11.  
  12. // Szybkie potęgowanie do odwracania modulo
  13. int fast_pow(int base, int exp) {
  14.     int res = 1;
  15.     while (exp > 0) {
  16.         if (exp % 2 == 1) res = (res * base) % MOD;
  17.         base = (base * base) % MOD;
  18.         exp /= 2;
  19.     }
  20.     return res;
  21. }
  22.  
  23. // Inicjalizacja silni
  24. void precompute() {
  25.     fact[0] = 1;
  26.     for (int i = 1; i < MAX; i++) fact[i] = (fact[i - 1] * i) % MOD;
  27.     invFact[MAX - 1] = fast_pow(fact[MAX - 1], MOD - 2);
  28.     for (int i = MAX - 2; i >= 0; i--) invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
  29. }
  30.  
  31. // Obliczanie permutacji k-elementowych ze zbioru n-elementowego (n silnia / (n-k) silnia)
  32. // To jest to samo co: Symbol Newtona(n, k) * k!
  33. int perm(int n, int k) {
  34.     if (k < 0 || k > n) return 0;
  35.     return (fact[n] * invFact[n - k]) % MOD;
  36. }
  37.  
  38. int32_t main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(NULL);
  41.  
  42.     precompute();
  43.  
  44.     int n, m;
  45.     if (!(cin >> n >> m)) return 0;
  46.     string s;
  47.     cin >> s;
  48.  
  49.     // 1. Grupowanie w bloki (Znak, Długość)
  50.     vector<pair<char, int>> blocks;
  51.     if (m > 0) {
  52.         char current_char = s[0];
  53.         int count = 1;
  54.         for (int i = 1; i < m; i++) {
  55.             if (s[i] == current_char) {
  56.                 count++;
  57.             } else {
  58.                 blocks.push_back({current_char, count});
  59.                 current_char = s[i];
  60.                 count = 1;
  61.             }
  62.         }
  63.         blocks.push_back({current_char, count});
  64.     }
  65.  
  66.     // 2. Symulacja
  67.     priority_queue<int> pool;      // Wolne drzewa (największe priorytetem)
  68.     priority_queue<int> active;    // Podlane drzewa (największe priorytetem)
  69.  
  70.     for (int i = 1; i <= n; i++) pool.push(i);
  71.  
  72.     int total_coins = 0;
  73.     int scenarios = 1;
  74.  
  75.     for (auto block : blocks) {
  76.         char type = block.first;
  77.         int len = block.second;
  78.  
  79.         if (type == 'C') {
  80.             // Możemy podlać tyle, ile mamy wolnych, ale nie więcej niż długość bloku
  81.             int k = min((int)pool.size(), len);
  82.  
  83.             // Matematyka: Z 'len' dostępnych dni wybieramy 'k' i obsadzamy konkretnymi drzewami
  84.             // Sposoby: len! / (len-k)!
  85.             if (k > 0) {
  86.                 scenarios = (scenarios * perm(len, k)) % MOD;
  87.  
  88.                 // Przenosimy k najlepszych drzew
  89.                 for (int i = 0; i < k; i++) {
  90.                     active.push(pool.top());
  91.                     pool.pop();
  92.                 }
  93.             }
  94.         } else { // type == 'Z'
  95.             // Możemy zebrać tyle, ile jest aktywnych, ale nie więcej niż długość bloku
  96.             int k = min((int)active.size(), len);
  97.  
  98.             // Matematyka: Z 'len' dni wybieramy 'k' na zbiory
  99.             if (k > 0) {
  100.                 scenarios = (scenarios * perm(len, k)) % MOD;
  101.  
  102.                 vector<int> harvested;
  103.                 // Zbieramy k najlepszych drzew (bo chcemy zmaksymalizować wynik i szybko je zwolnić)
  104.                 for (int i = 0; i < k; i++) {
  105.                     int tree = active.top();
  106.                     active.pop();
  107.                     total_coins += tree;
  108.                     harvested.push_back(tree);
  109.                 }
  110.  
  111.                 // Od razu wracają do puli (bo w kolejnym bloku C mogą być podlane)
  112.                 for (int tree : harvested) {
  113.                     pool.push(tree);
  114.                 }
  115.             }
  116.         }
  117.     }
  118.  
  119.     cout << total_coins << " " << scenarios << "\n";
  120.  
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 6664KB
comments (?)
stdin
copy 
2026 20
CCCCCCCCZZZZZZZZZZZZ
stdout
copy 
16180 722682372
https://ideone.com/gCVDoD
language:
C++14 (gcc 8.3)
created:
13 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!