Submission #1691822

---

Source Code Expand

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;
typedef long long LL;
const int maxn = 2005;
const int mod = 924844033;

int h[maxn][maxn];
int g[maxn][maxn];
int f[maxn],e[maxn],v[maxn];
int n,fac[maxn],inc[maxn],sz[maxn],K;

LL fpm(LL p,LL k) {
	LL res=1ll;
	while (k) {
		if (k&1) (res*=p)%=mod;
		(p*=p)%=mod;k>>=1;
	}
	return res;
}
LL comb(int n,int m) {
	return (LL)fac[n]*inc[m]%mod*(LL)inc[n-m]%mod;
}
int main()
{
	#ifdef Amberframe
		freopen("agc005d.in","r",stdin);
		freopen("agc005d.out","w",stdout);
	#endif
	scanf("%d %d",&n,&K);fac[0]=inc[0]=1;
	for (int i=1;i<=n;i++)
	{
		if (i-2*K<=0) {
			sz[i]=1;g[i][0]=1;g[i][1]=(i>K);h[i][1]=(i+K<=n);
		}
		else {
			int o=i-2*K;sz[i]=sz[o]+1;
			for (int j=0;j<=sz[i];j++)
				g[i][j]=(g[o][j]+h[o][j])%mod;
			for (int j=1;j<=sz[i];j++)
				g[i][j]=(g[i][j]+g[o][j-1])%mod;
			if (i+K>n) continue;
			for (int j=1;j<=sz[i];j++)
				h[i][j]=(g[o][j-1]+h[o][j-1])%mod;
		}
	}
	
	for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%mod;
	inc[n]=fpm(fac[n],mod-2);
	for (int i=n;i>=2;i--) inc[i-1]=(LL)inc[i]*i%mod;
	
	f[0]=1;int sum=0;
	for (int i=1;i<=n;i++)
	if (i+2*K>n) {
		for (int k=sz[i];k>=0;k--)
			e[k]=(h[i][k]+g[i][k])%mod;
		for (int k=sum+sz[i];k>=0;k--) v[k]=0;
		for (int j=sum;j>=0;j--)
		for (int k=sz[i];k>=0;k--)
			v[j+k]=(v[j+k]+(LL)f[j]*e[k])%mod;
		for (int k=sum+sz[i];k>=0;k--) f[k]=v[k];
		sum+=sz[i];
	}
	
	for (int i=0;i<=n;i++)
		f[i]=(LL)f[i]*fac[n-i]%mod;
	for (int i=n-1;i>=0;i--)
	for (int j=i+1;j<=n;j++)
		f[i]=(f[i]-(LL)f[j]*comb(j,i))%mod;
	printf("%d",f[0]<0?f[0]+mod:f[0]);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:33:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&K);fac[0]=inc[0]=1;
                      ^

Judge Result