Submission #18379015

---

Source Code Expand

/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define mod 924844033
#define int long long
using namespace std;
const int N=2100;
int n,k,dp[N][N][3];
int all[N],fac[N];
inline void add(int &a,int b){a=((a+b)>mod?a+b-mod:a+b);}
inline void del(int &a,int b){a=((a-b<0)?a-b+mod:a-b);}
inline void mul(int &a,int b){a=(a*b)%mod;}
inline int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) mul(ans,a);
		b>>=1;
		mul(a,a);
	}
	return ans;
}
inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
inline int cal(int x){return(x-k>0)+(x+k<=n);}
signed main()
{
	n=read();k=read();
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	int sum=0;all[0]=1;
	for (int i=1;i<=min(2*k,n);i++)
	{
		dp[1][0][2]=1;
		if (cal(i)==0) dp[1][1][0]=dp[1][1][1]=0;
		if (cal(i)==1) dp[1][1][1]=1,dp[1][1][0]=0;
		if (cal(i)==2) dp[1][1][0]=dp[1][1][1]=1;
		int w=1;sum++;
		for (int j=i+2*k;j<=n;j+=2*k)
		{
			w++;sum++;
			for (int p=0;p<=w;p++)
			{
				dp[w][p][0]=dp[w][p][1]=dp[w][p][2]=0;
				add(dp[w][p][2],dp[w-1][p][0]);add(dp[w][p][2],dp[w-1][p][1]);add(dp[w][p][2],dp[w-1][p][2]);
				if (!p) continue;
				add(dp[w][p][0],dp[w-1][p-1][2]);
				add(dp[w][p][0],dp[w-1][p-1][0]);
				if (cal(j)==2)
				{
					add(dp[w][p][1],dp[w-1][p-1][2]);
					add(dp[w][p][1],dp[w-1][p-1][0]);add(dp[w][p][1],dp[w-1][p-1][1]);
				}
			}
		}
		for (int j=sum;j>=1;j--)
		{
			for (int k=1;k<=min(w,j);k++) add(all[j],all[j-k]*(dp[w][k][0]+dp[w][k][1]+dp[w][k][2])%mod);
		}
	}
	int ans=0;
	for (int i=0;i<=n;i++)
	{
		if (i&1) del(ans,fac[n-i]*all[i]%mod);
		else add(ans,fac[n-i]*all[i]%mod);
	}
//	for (int i=0;i<=n;i++) printf("%lld ",all[i]);
//	printf("\n");
	printf("%lld\n",ans);
}

Submission Info

Judge Result