Advertisement
wym1111

Untitled

Oct 30th, 2024
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. //#define int long long
  5. using ll = long long;
  6. const int N = 5e2 + 10;
  7. const ll mod = 998244353;
  8.  
  9. int n, m;
  10. ll dp[2][N][N], f[N];
  11. ll ans[N][N];
  12.  
  13. void init () {
  14.     cin >> n >> m;
  15.    
  16.     f[0] = 1;
  17.     for (int i = 1; i <= m; i ++) {
  18.         for (int j = i; j >= (i + 1) / 2; j --) {
  19.             f[j] = (f[j] + f[j - 1]) % mod;
  20.         }
  21.         for (int j = 0; j < (i + 1) / 2; j ++) f[j] = 0;
  22.     }
  23.     for (int i = 0; i <= m; i += 2) {
  24.         ans[1][i] = f[i + (m - i) / 2];
  25.     }
  26. }
  27.  
  28. void solve () {
  29.     init();
  30.    
  31. //  for (int i = 0; i <= m; i ++) {
  32. //      cout << i << ' ' << ans[1][i] << endl;
  33. //  }
  34.    
  35.     memset(dp, 0, sizeof dp);
  36.     dp[0][0][0] = 1;
  37.     for (int i = 1; i <= m; i ++) {
  38.         int cur = i & 1;
  39.         int lst = cur ^ 1;
  40.         for (int j = 0; j < i; j ++) {
  41.             for (int k = 0; k <= m; k ++) {
  42.                 dp[cur][j + 1][k] = (dp[cur][j + 1][k] + dp[lst][j][k]) % mod;
  43.                 if (j) dp[cur][j - 1][k] = (dp[cur][j - 1][k] + dp[lst][j][k]) % mod;
  44.                 else dp[cur][j][k + 1] = (dp[cur][j][k + 1] + dp[lst][j][k]) % mod;
  45.             }
  46.         }
  47.         for (int j = 0; j <= m; j ++) {
  48.             for (int k = 0; k <= m; k ++) {
  49.                 dp[lst][j][k] = 0;
  50.             }
  51.         }
  52.     }
  53.     for (int j = 0; j <= m; j ++) {
  54.         f[j] = dp[0][0][j];
  55. //      cout << f[j] << " \n"[j == m];
  56.     }
  57.    
  58.    
  59.     for (int i = 2; i <= n; i ++) {
  60.         for (int j = 0; j <= m; j ++) {
  61.             for (int k = 0; k <= j; k ++) {
  62.                 ans[i][j - k] = (ans[i][j - k] + ans[i - 1][j] * f[k] % mod) % mod;
  63.             }
  64.         }
  65.     }
  66.    
  67.     cout << ans[n][0] << endl;
  68. }
  69.  
  70. signed main () {
  71.     ios::sync_with_stdio(0);
  72.     cin.tie(0);
  73.    
  74.     int _ = 1;
  75. //  cin >> _;
  76.     while (_ --) {
  77.         solve();
  78.     }
  79.    
  80.     return 0;
  81. }
  82.  
  83.  
  84. /*
  85.   1: 1 2 3 4
  86.   2: 1 2 3 4
  87.   3: 1 2 3 4
  88.   4: 1 2 3 4
  89.   5: 1 2 3 4
  90.  
  91.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement