Submission #7942347

---

Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
#define mod 924844033
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
int f[2010],fact[2010],ifact[2010];
int C(int n,int m){if(n<m)return 0;return 1ll*fact[n]*ifact[m]%mod*ifact[n-m]%mod;}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi(),K=gi();
	fact[0]=1;for(int i=1;i<=n;++i)fact[i]=1ll*fact[i-1]*i%mod;
	ifact[n]=pow(fact[n],mod-2);for(int i=n;i;--i)ifact[i-1]=1ll*ifact[i]*i%mod;
	f[0]=1;
	for(int l=1;l<=n&&l<=K*2;++l){
		int r=l;while(r+K*2<=n)r+=K*2;
		int cnt=(r-l)/K+(l>K)+(r+K<=n);
		for(int i=n;i;--i)
			for(int j=1;j*2-1<=cnt&&j<=i;++j)
				f[i]=(f[i]+1ll*f[i-j]*C(cnt-j+1,j))%mod;
	}
	int ans=0;
	for(int i=0,m=1;i<=n;++i,m=mod-m)ans=(ans+1ll*f[i]*m%mod*fact[n-i])%mod;
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result