fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(v) v.begin(),v.end()
  4. #define MASK(i) (1LL << (i))
  5. #define ii pair<int,int>
  6. #define fi first
  7. #define se second
  8. #define endl '\n'
  9. using namespace std;
  10.  
  11. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  12. #define rand rd
  13.  
  14. long long Rand(long long l , long long h){
  15. 	assert(l <= h);
  16. 	return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
  17. }
  18.  
  19. const int MAX = 4e3 + 5 , MOD = 998244353;
  20. int n;
  21. short a[MAX];
  22. int dp[MAX][MAX];
  23. int presum[MAX][MAX];
  24.  
  25. void add(int &x , int y){
  26.     x = x + y;
  27.     if(x >= MOD) x = x - MOD;
  28. }
  29.  
  30. void INP(){
  31.     {
  32.         string tmp;
  33.         cin >> tmp;
  34.         n = tmp.size();
  35.         for(int i = 1 ; i <= n ; i++) a[i] = int(tmp[i - 1]) - int('a');
  36.     }
  37.     for(int i = 1 ; i <= n ; i++){
  38.         for(int j = n ; j >= i ; j--){
  39.             if(a[i] == a[j]){
  40.                 dp[i][j] = presum[i - 1][j + 1];
  41.                 add(dp[i][j] , 1);
  42.             }
  43.         }
  44.         for(int j = n ; j >= i ; j--){
  45.             presum[i][j] = presum[i - 1][j];
  46.             add(dp[i][j] , dp[i][j + 1]);
  47.             add(presum[i][j] , dp[i][j]);
  48.         }
  49.     }
  50.     for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= n ; j++) dp[i][j] = 0;
  51.     for(int i = n ; i >= 1 ; i--){
  52.         for(int j = i ; j <= n ; j++){
  53.             if(a[i] == a[j]){
  54.                 dp[i][j] = 1;
  55.                 add(dp[i][j] , dp[i + 1][j - 1]);
  56.             }
  57.         }
  58.         int congthem = 0;
  59.         for(int j = i ; j <= n ; j++){
  60.             int tmp = congthem;
  61.             add(congthem , dp[i][j]);
  62.             add(dp[i][j] , tmp);
  63.             add(dp[i][j] , dp[i + 1][j]);
  64.         }
  65.     }
  66.  
  67.     for(int i = 1 ; i <= n ; i++){
  68.         int res = 1;
  69.         add(res , presum[i - 1][i + 1]);
  70.         for(int j = 1 ; j < i ; j++) if(a[j] == a[i]){
  71.             add(res , 1ll * (presum[j - 1][i + 1] + 1) * (dp[j + 1][i - 1] + 1) % MOD);
  72.         }
  73.         for(int j = n ; j > i ; j--) if(a[i] == a[j]){
  74.             add(res , 1ll * (presum[i - 1][j + 1] + 1) * (dp[i + 1][j - 1] + 1) % MOD);
  75.         }
  76.         cout << res << ' ';
  77.     }
  78. }
  79.  
  80. int main()
  81. {
  82.     ios_base::sync_with_stdio(false);
  83.     cin.tie(0);
  84.     cout.tie(0);
  85.     #define TASK ""
  86.     //freopen(TASK".inp" , "r" , stdin);
  87.     //freopen(TASK".out" , "w" , stdout);
  88.     INP();
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uzDc2U
language:
C++14 (gcc 8.3)
created:
11 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!