Submission #3623495

---

Source Code Expand

// In the name of God

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=4010,mod=998244353;
const ll inf=1e18;

int ans[maxn],fac[maxn],ifac[maxn],tw[maxn];

int Pow(int a,int b){
    int ans=1;
    while(b){
	if(b&1)	ans=1ll*ans*a %mod;
	a=1ll*a*a %mod;
	b>>=1;
    }
    return ans;
}

inline int C(int n,int k){
    if(n<k) return 0;
    return 1ll*fac[n]*ifac[k] %mod *ifac[n-k] %mod;
}

int solve(int n,int x){// x1+x2+x3+...+xn == x // xi>=0
    return C(n+x-1,n-1);
}

int main(){
    fac[0]=1;
    for(int i=1;i<maxn;i++)
	fac[i]=1ll*fac[i-1]*i %mod;
    ifac[maxn-1]=Pow(fac[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--)
	ifac[i]=1ll*ifac[i+1]*(i+1) %mod;
    tw[0]=1;
    for(int i=1;i<maxn;i++)
	tw[i]=2ll*tw[i-1] %mod;
    
    int k,n;cin>>k>>n;
    for(int i=2;i<=k+1;i++){
	int cnt=(i/2)-((i&1)==0);
	for(int j=0;j<=cnt;j++){
	    ans[i]=(1ll*ans[i]+1ll*C(cnt,j)*tw[j] %mod *(solve(k-2*(cnt-j)-j-((i&1)==0),n-j)+((i&1)?0:solve(k-2*(cnt-j)-j-1,n-j-1))))%mod;
	}
    }   
    
    for(int i=2;i<=k+1;i++)
	cout<<ans[i]<<"\n";
    for(int i=k;i>=2;i--)
	cout<<ans[i]<<"\n";
}

Submission Info

Judge Result