Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- //#define int long long
- using ll = long long;
- const int N = 5e2 + 10;
- const ll mod = 998244353;
- int n, m;
- ll dp[2][N][N], f[N];
- ll ans[N][N];
- void init () {
- cin >> n >> m;
- f[0] = 1;
- for (int i = 1; i <= m; i ++) {
- for (int j = i; j >= (i + 1) / 2; j --) {
- f[j] = (f[j] + f[j - 1]) % mod;
- }
- for (int j = 0; j < (i + 1) / 2; j ++) f[j] = 0;
- }
- for (int i = 0; i <= m; i += 2) {
- ans[1][i] = f[i + (m - i) / 2];
- }
- }
- void solve () {
- init();
- // for (int i = 0; i <= m; i ++) {
- // cout << i << ' ' << ans[1][i] << endl;
- // }
- memset(dp, 0, sizeof dp);
- dp[0][0][0] = 1;
- for (int i = 1; i <= m; i ++) {
- int cur = i & 1;
- int lst = cur ^ 1;
- for (int j = 0; j < i; j ++) {
- for (int k = 0; k <= m; k ++) {
- dp[cur][j + 1][k] = (dp[cur][j + 1][k] + dp[lst][j][k]) % mod;
- if (j) dp[cur][j - 1][k] = (dp[cur][j - 1][k] + dp[lst][j][k]) % mod;
- else dp[cur][j][k + 1] = (dp[cur][j][k + 1] + dp[lst][j][k]) % mod;
- }
- }
- for (int j = 0; j <= m; j ++) {
- for (int k = 0; k <= m; k ++) {
- dp[lst][j][k] = 0;
- }
- }
- }
- for (int j = 0; j <= m; j ++) {
- f[j] = dp[0][0][j];
- // cout << f[j] << " \n"[j == m];
- }
- for (int i = 2; i <= n; i ++) {
- for (int j = 0; j <= m; j ++) {
- for (int k = 0; k <= j; k ++) {
- ans[i][j - k] = (ans[i][j - k] + ans[i - 1][j] * f[k] % mod) % mod;
- }
- }
- }
- cout << ans[n][0] << endl;
- }
- signed main () {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int _ = 1;
- // cin >> _;
- while (_ --) {
- solve();
- }
- return 0;
- }
- /*
- 1: 1 2 3 4
- 2: 1 2 3 4
- 3: 1 2 3 4
- 4: 1 2 3 4
- 5: 1 2 3 4
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement