Submission #4019243

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MAX_COMB = 5000;
const LL mod = 998244353;
LL fct[MAX_COMB+1];
LL invfct[MAX_COMB+1];

void build(){
	fct[0] = fct[1] = 1;
	repp(i,2,MAX_COMB+1){
		fct[i] = fct[i-1] * i % mod;
	}
	LL x = fct[MAX_COMB];
	invfct[MAX_COMB] = 1;
	for(int i = mod - 2 ; i > 0 ; i >>= 1){
		if(i % 2 == 1) (invfct[MAX_COMB] *= x) %= mod;
		(x *= x) %= mod;
	}
	repm(i,MAX_COMB,0){
		invfct[i-1] = invfct[i] * i % mod;
	}
}

LL comb(int x , int y){
	if(x < 0 || y < 0 || x < y) return 0;
	return fct[x] * invfct[y] % mod * invfct[x-y] % mod;
}

int main(){
	build();
	int K,N; cin >> K >> N;
	vector<LL> ans(2*K+1,0);
	vector<LL> dp(N+1,0);
	dp[0] = 1;
	repp(i,2,K+2){
		if(i&1){
			vector<LL> nx(N+1,0);
			LL s = 0;
			repp(j,0,N+1){
				nx[j] = (s+dp[j])%mod;
				s = (s+2*dp[j])%mod;
			}
			swap(dp,nx);
			repp(j,0,N+1) (ans[i] += dp[j]*comb(N-j+K-i,N-j)) %= mod;
			if(i == K+1) ans[i] = dp[N];
		} else {
			repp(j,0,N) (ans[i] += dp[j]*(comb(N-j+K-i,N-j)+comb(N-j+K-i-1,N-j-1))) %= mod;
			(ans[i] += dp[N]) %= mod;
			if(i == K+1) ans[i] = (dp[N-1]+dp[N])%mod;
		}
		
		ans[2*K+2-i] = ans[i];
	}
	repp(i,2,2*K+1) cout << ans[i] << endl;
	return 0;
}

Submission Info

Judge Result