Submission #43542854

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 410,mod = 998244353;

void add(ll& x,ll y){x=(x+y)%mod;}
ll addv(ll x,ll y){return (x+y)%mod;}

int n,m;

ll dp[2][MAXN][MAXN],f[MAXN][MAXN],sf[MAXN],g[MAXN][MAXN][2],C[MAXN][MAXN];

int main(){
	C[0][0]=1;
	rep(i,1,400){
		C[i][0]=1;
		rep(j,1,i)C[i][j] = addv(C[i-1][j-1],C[i-1][j]);
	}

	cin>>n>>m;

	per(i,n,1){
		memset(f,0,sizeof f);
		memset(g,0,sizeof g);
		memset(sf,0,sizeof sf);

		rep(j,1,m){
			rep(c,1,m)add(f[j][c],dp[(i+1)&1][j][c]);
			per(c,m,1)add(f[j][c],f[j][c+1]);

			add(sf[j],f[j][1]);
		}
		rep(j,1,m)add(sf[j],sf[j-1]);
		
		rep(j,1,m){
			rep(c,1,m)add(g[j][c][1],f[j][c]);
			add(g[j][1][1],sf[j-1]);
		}

		rep(j,1,m)rep(c,1,m)rep(k,0,1){
			add(g[j+1][c][0],g[j][c][k]);
			add(g[j+1][c+1][1],g[j][c][k]);
		}

		rep(j,1,m)rep(c,1,m){
			add(dp[i&1][j][c],g[j][c][1]);
			add(dp[i&1][j][c],C[j-1][c-1]);
			add(dp[i&1][j][c],dp[(i+1)&1][j][c]);



			dp[(i+1)&1][j][c] = 0;
		}
	}

	ll ans = 1;
	rep(j,1,m)rep(c,1,m)add(ans,dp[1][j][c]);

	cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result