fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. const int MOD = 998244353;
  10. const int MAXN = 400005;
  11.  
  12. long long fact[MAXN], inv_fact[MAXN], pow2[MAXN];
  13.  
  14. long long power(long long base, long long exp) {
  15.     long long res = 1;
  16.     base %= MOD;
  17.     while (exp > 0) {
  18.         if (exp % 2 == 1) res = (res * base) % MOD;
  19.         base = (base * base) % MOD;
  20.         exp /= 2;
  21.     }
  22.     return res;
  23. }
  24.  
  25. void precompute() {
  26.     fact[0] = 1;
  27.     inv_fact[0] = 1;
  28.     pow2[0] = 1;
  29.     for (int i = 1; i < MAXN; ++i) {
  30.         fact[i] = (fact[i - 1] * i) % MOD;
  31.         pow2[i] = (pow2[i - 1] * 2) % MOD;
  32.     }
  33.     inv_fact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2);
  34.     for (int i = MAXN - 2; i >= 1; --i) {
  35.         inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
  36.     }
  37. }
  38.  
  39. long long C(int n, int k) {
  40.     if (k < 0 || k > n) return 0;
  41.     return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
  42. }
  43.  
  44. long long get_G(int n, int k) {
  45.     if (n < 0) return 0;
  46.     long long G = 0;
  47.     for (int m = 0; m * (k + 2) <= n; ++m) {
  48.         long long term = C(n - m * (k + 1), m);
  49.         term = (term * pow2[n - m * (k + 2)]) % MOD;
  50.         if (m % 2 == 1) {
  51.             G = (G - term + MOD) % MOD;
  52.         } else {
  53.             G = (G + term) % MOD;
  54.         }
  55.     }
  56.     return G;
  57. }
  58.  
  59. long long W(int D, int k) {
  60.     long long g_d1 = get_G(D + 1, k);
  61.     long long g_d = get_G(D, k);
  62.     return (g_d1 - g_d + MOD) % MOD;
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(NULL);
  68.     precompute();
  69.  
  70.     int N;
  71.     if (!(cin >> N)) return 0;
  72.     string S;
  73.     cin >> S;
  74.  
  75.     vector<int> blocks;
  76.     int current_len = 0;
  77.     for (int i = 0; i < N; ++i) {
  78.         if (S[i] == '.') {
  79.             current_len++;
  80.         } else {
  81.             if (current_len > 0) {
  82.                 blocks.push_back(current_len);
  83.                 current_len = 0;
  84.             }
  85.         }
  86.     }
  87.     if (current_len > 0) blocks.push_back(current_len);
  88.  
  89.     map<int, int> freq;
  90.     for (int b : blocks) freq[b]++;
  91.  
  92.     vector<pair<int, int>> unique_blocks(freq.begin(), freq.end());
  93.  
  94.     vector<long long> F(N + 1, 0);
  95.     F[0] = 1; 
  96.  
  97.     long long current_pow2_sum = 0;
  98.     int block_idx = 0;
  99.  
  100.     for (int k = 1; k <= N; ++k) {
  101.         while (block_idx < unique_blocks.size() && unique_blocks[block_idx].first <= k) {
  102.             current_pow2_sum += 1LL * unique_blocks[block_idx].first * unique_blocks[block_idx].second;
  103.             block_idx++;
  104.         }
  105.  
  106.         long long ways = pow2[current_pow2_sum];
  107.  
  108.         for (int i = block_idx; i < unique_blocks.size(); ++i) {
  109.             int D = unique_blocks[i].first;
  110.             int count = unique_blocks[i].second;
  111.  
  112.             long long w_val = W(D, k);
  113.             long long term = power(w_val, count);
  114.             ways = (ways * term) % MOD;
  115.         }
  116.         F[k] = ways;
  117.     }
  118.  
  119.     for (int k = 1; k <= N; ++k) {
  120.         long long ans = (F[k] - F[k - 1] + MOD) % MOD;
  121.         cout << ans << "\n";
  122.     }
  123.  
  124.     return 0;
  125. }
Success #stdin #stdout 0.01s 12944KB
comments (?)
stdin
copy 
7
.......
stdout
copy 
33
47
27
12
5
2
1
https://ideone.com/00rkQ8
language:
C++14 (gcc 8.3)
created:
2 days 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!