Submission #25258605

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define WT int TT=read();while(TT--) 
#define NO puts("NO");
#define YES puts("YES");
using namespace std;

inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

const int Mod=924844033;
const int M=2010;
int fac[M],ifac[M],n,k,tmp[M],ans[M],sz,a2[M];

int poww(int a,int b)
{
	int res=1;
	while(b)
	{
		if (b&1)res=res*a%Mod;
		a=a*a%Mod,b>>=1;
	}return res;
}
int inv(int x){return poww(x,Mod-2);}
void init(int n)
{
	fac[0]=ifac[0]=1;
	for (int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%Mod,
		ifac[i]=inv(fac[i]);
}
int C(int m,int n)
{
	if (m<0||n<0||m<n)return 0;
	return fac[m]*ifac[n]%Mod*ifac[m-n]%Mod;
}

signed main()
{
	n=read(),k=read();init(n);ans[0]=1,sz=0;
	for (int w=1;w<=2*k;w++)
	{
		int s1=(n-(w>k?w-k:w))/k+1;
		memset(tmp,0,sizeof(tmp));
		for (int i=0;i<=s1/2;i++)a2[i]=C(s1-i,i);
		for (int i=0;i<=sz;i++)
			for (int j=0;j<=s1/2;j++)
				tmp[i+j]=(tmp[i+j]+ans[i]*a2[j])%Mod;
		sz+=s1/2;for (int i=0;i<=sz;i++)ans[i]=tmp[i];
	}int res=0;
	for (int i=0;i<=n;i++)res=(res+ans[i]*poww(Mod-1,i)%Mod*fac[n-i])%Mod;
	cout<<res<<endl;
	return 0;
}

Submission Info

Judge Result