Submission #5895028

---

Source Code Expand

#include "bits/stdc++.h"

using namespace std;

int N,M,K,L,R,H,W;

//const long long int MOD=1000000007;
const long long int MOD=998244353;

long long int power(long long int x, long long int n, long long int M) {
	long long int ret = 1;
	long long int by = x;
	while (n) {
		if (n & 1) {
			ret *= by;
			ret %= M;
		}
		by *= by;
		by %= M;
		n >>= 1;
	}
	return ret;
}

int main(){
	
	cin>>N>>M;
	vector<vector<long long int>>dp(N+1,vector<long long int>(2*N+1));
	dp[0][0]=1;
	for(int i=0;i<N;i++){
		for(int j=i;j<=i*2;j++){
			dp[i+1][j+1]+=dp[i][j];
			dp[i+1][j+1]%=MOD;
			dp[i+1][j+2]+=dp[i][j];
			dp[i+1][j+2]%=MOD;
		}
	}
	vector<long long int>num(N+1);
	for(int i=0;i<=N;i++){
		for(int j=0;j<M;j++){
			num[i]+=dp[i][j];
			num[i]%=MOD;
		}
	}
	if(M&1){
		for(int i=M+1;i<=2*N;i+=2){
			num[i/2]++;
		}
	}
	//cout<<"hoge"<<endl;
	vector<long long int>by(N+1,1);
	vector<long long int>rev(N+1,1);
	for(int i=2;i<=N;i++){
		by[i]=by[i-1]*i;
		by[i]%=MOD;
		rev[i]=power(by[i],MOD-2,MOD);
	}
	for(int i=0;i<=N;i++){
	//	cout<<i<<" "<<num[i]<<endl;
	}
	for(int i=2;i<M-1;i+=2){
		if(M-1-i<0)break;
		for(int j=1;j<=N;j++){
			if(j+i>N)break;
			num[j+i]+=dp[j][M-1-i];
			num[j+i]%=MOD;
		}
	}
	long long int ans=0;
	for(int i=0;i<=N;i++){
	//	cout<<i<<" "<<num[i]<<endl;
		long long int add=by[N];
		add*=rev[i];
		add%=MOD;
		add*=rev[N-i];
		add%=MOD;
		add*=num[i];
		add%=MOD;
		ans+=add;
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result