AtCoder Grand Contest 005

Submission #1586125

Source codeソースコード

#include<iostream>
#include<cstdio>
#include<cstring>
namespace bigger
{
	typedef long long ll;
	const int N=2010,MOD=924844033;
	inline void inc(ll a,ll &b){b=(a+b)%MOD;}
	ll inv(ll x){return x<=1?1:((MOD-(MOD/x)*inv(MOD%x)%MOD)%MOD);}
	ll f[N][N][2][2],A[N],B[N],C[N];
	int n,k;
	void initialize()
	{
		scanf("%d%d",&n,&k);
		int n0=k-(n%k),n1=n%k,len=n/k+1;
		f[1][0][0][0]=f[1][1][0][1]=1;
		for(int i=1;i<=len;i++)
			for(int j=0;j<=i;j++)
			{
				ll v00=f[i][j][0][0],v01=f[i][j][0][1],v10=f[i][j][1][0],v11=f[i][j][1][1];

				inc(v00,f[i+1][j][0][0]);
				inc(v00,f[i+1][j+1][0][0]);
				inc(v00,f[i+1][j+1][0][1]);

				inc(v01,f[i+1][j][1][0]);
				inc(v01,f[i+1][j+1][1][0]);
				inc(v01,f[i+1][j+1][1][1]);
				
				inc(v10,f[i+1][j][0][0]);
				inc(v10,f[i+1][j+1][0][1]);

				inc(v11,f[i+1][j][1][0]);
				inc(v11,f[i+1][j+1][1][1]);
			}
		int tot=0;C[0]=1;

		for(int i=0;i<=len;i++)A[i]=(f[len][i][0][0]+f[len][i][1][0])%MOD;
		while(n1--)
		{
			for(int i=0;i<=tot+len;i++)B[i]=0;
			for(int i=0;i<=len;i++)
				for(int j=0;j<=tot;j++)
					inc(A[i]*C[j]%MOD,B[i+j]);
			tot+=len;
			for(int i=0;i<=tot;i++)C[i]=B[i];
		}
		len--;
		for(int i=0;i<=len;i++)A[i]=(f[len][i][0][0]+f[len][i][1][0])%MOD;
		while(n0--)
		{
			for(int i=0;i<=tot+len;i++)B[i]=0;
			for(int i=0;i<=len;i++)
				for(int j=0;j<=tot;j++)
					inc(A[i]*C[j]%MOD,B[i+j]);
			tot+=len;
			for(int i=0;i<=tot;i++)C[i]=B[i];
		}
//		printf("tot = %d\n",tot);
	}
	void solve()
	{
		initialize();
//		for(int i=0;i<=n;i++)printf("%lld ",C[i]);printf("\n");

		ll fact=1,ans=0;
		for(int i=1;i<=n;i++)fact=fact*i%MOD;
		for(int i=0;i<=n;i++)
		{
			if(i&1)ans=(ans-C[i]*fact%MOD)%MOD;
			else ans=(ans+C[i]*fact%MOD)%MOD;
			fact=fact*inv(n-i)%MOD;
		}
		printf("%lld\n",(ans%MOD+MOD)%MOD);
	}
}
int main()
{
	bigger::solve();
	return 0;
}

Submission

Task問題 D - ~K Perm Counting
User nameユーザ名 Demerzel_IV
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 900
Source lengthソースコード長 1906 Byte
File nameファイル名
Exec time実行時間 54 ms
Memory usageメモリ使用量 124288 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘void bigger::initialize()’:
./Main.cpp:14:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2,example3,example4
All 900 / 900 example0,example1,example2,example3,example4,handmade0,handmade1,handmade2,handmade3,handmade4,handmade5,handmade6,maxrand0,maxrand1,maxrand2,maxrand3,maxrand4,rand0,rand1,rand2,rand3,rand4,small0,small1,small2,supersmall0,supersmall1,supersmall2

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
example0 AC 1 ms 256 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
example3 AC 1 ms 256 KB
example4 AC 2 ms 256 KB
handmade0 AC 1 ms 256 KB
handmade1 AC 54 ms 124288 KB
handmade2 AC 17 ms 256 KB
handmade3 AC 49 ms 117120 KB
handmade4 AC 15 ms 256 KB
handmade5 AC 9 ms 2432 KB
handmade6 AC 9 ms 2432 KB
maxrand0 AC 15 ms 256 KB
maxrand1 AC 12 ms 256 KB
maxrand2 AC 12 ms 256 KB
maxrand3 AC 8 ms 4480 KB
maxrand4 AC 16 ms 256 KB
rand0 AC 10 ms 256 KB
rand1 AC 2 ms 256 KB
rand2 AC 3 ms 256 KB
rand3 AC 1 ms 256 KB
rand4 AC 13 ms 256 KB
small0 AC 1 ms 256 KB
small1 AC 1 ms 256 KB
small2 AC 1 ms 256 KB
supersmall0 AC 1 ms 256 KB
supersmall1 AC 1 ms 256 KB
supersmall2 AC 1 ms 256 KB