結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー kuuso1kuuso1
提出日時 2015-08-30 13:54:56
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 24 ms / 3,000 ms
コード長 5,962 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 28,364 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-25 19:47:36
合計ジャッジ時間 789 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 13 ms
4,376 KB
testcase_01 AC 24 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#define Long long long int
Long dpP[301][4000];
Long dpC[301][4000];

//kitamasa
int K;
Long Rel[8000];
Long mod;

void ModPolynomial_m_init(Long rel[],int mod_,int k_){
	// usage: ak=rel[0]*a0+...+rel[k-1]*a(k-1);
	// T^k=rel[0]*1+rel[1]*T^1+...+rel[k-1]*T^(k-1);
	int i;
	K=k_;
	for(i=0;i<K;i++)Rel[i]=rel[i];
	mod=mod_;
}


Long *Convolution_m(Long a[],Long b[],int aLen,int bLen,int *abLen){
	// calc. a*b (convolution) naive
	int L=aLen+bLen-1;
	*abLen=L;
	int i,j;
//printf("conv:a.Length=%d,a=",aLen);for(i=0;i<aLen;i++)printf(i==0?"%lld":" %lld",a[i]);puts("");	
//printf("conv:b.Length=%d,b=",bLen);for(i=0;i<bLen;i++)printf(i==0?"%lld":" %lld",b[i]);puts("");	
	Long *ret=(Long *)malloc(L*sizeof(Long));
	
	for(i=0;i<aLen;i++){
		if(a[i]==0)continue;
		for(j=0;j<bLen;j++){
			if(b[j]==0)continue;
			ret[i+j]+=a[i]*b[j];
			if(ret[i+j]>mod)ret[i+j]%=mod;
		}
	}
//printf("--->:r.Length=%d,r=",*abLen);for(i=0;i<*abLen;i++)printf(i==0?"%lld":" %lld",ret[i]);puts("");	
	return ret;
}

Long *Reduction_m(Long *a,int aLen,int *retLen){
	int i,j;
//printf("redu:a.Length=%d,a=",aLen);for(i=0;i<aLen;i++)printf(i==0?"%lld":" %lld",a[i]);puts("");	
	// reduce with Relation a(k)=rel[0]*a0+...+rel[k-1]*a(k-1);
	if(aLen<=K){*retLen=aLen;return a;}
	int N=aLen;
	//long[] ret0=(long[])a.Clone();
	Long *ret0=(Long *)malloc(aLen*sizeof(Long));
	for(i=0;i<aLen;i++)ret0[i]=a[i];
	
	// longer than K part
	for(i=N-1;i>=K;i--){
		if(ret0[i]==0)continue;
		for(j=0;j<K;j++){
			if(Rel[j]==0)continue;
			ret0[i-K+j]+=ret0[i]*Rel[j];
			if(ret0[i-K+j]>mod)ret0[i-K+j]%=mod;
		}
	}
	Long *ret=(Long *)malloc(K*sizeof(Long));
	for(i=0;i<K;i++)ret[i]=ret0[i];
	*retLen=K;
//printf("--->:r.Length=%d,r=",*retLen);for(i=0;i<*retLen;i++)printf(i==0?"%lld":" %lld",ret[i]);puts("");	
	return ret;
}


Long *Kitamasa_CalcModPolyT(Long k,int *len){
	int i;
	
	int retLen=1;
	Long *ret;
	ret=(Long *)malloc(retLen*sizeof(Long));
	ret[0]=1;
	
	int xLen=2;
	Long *x;
	x=(Long *)malloc(xLen*sizeof(Long));
	x[0]=0;x[1]=1;
	
	int cLen=0;
	while(k>0){
//printf("k=%lld,retLen=%d,ret=",k,retLen);for(i=0;i<retLen;i++)printf(i==0?"%lld":" %lld",ret[i]);printf("\n");
		if((k&1)==1){
			Long *retc=Convolution_m( ret,x,retLen,xLen,&cLen );
			ret=Reduction_m( retc,cLen,&retLen);
		}
		k=(k>>1);
		Long *xc=Convolution_m( x,x,xLen,xLen,&cLen );
		x=Reduction_m( xc,cLen,&xLen);
	}
	*len=retLen;
//printf("retLen=%d,ret=",retLen);for(i=0;i<retLen;i++)printf(i==0?"%lld":" %lld",ret[i]);printf("\n");
	return ret;
}

int main(){
	Long N;
	int P,C;
	int i,j,k;
	
	
	scanf("%lld %d %d",&N,&P,&C);
	
	int PDice[6]={2,3,5,7,11,13};
	int CDice[6]={4,6,8,9,10,12};
	mod=(Long)1e9+7;
	
	// dpP[n][val]:n回の出目でvalになる組み合わせ
	dpP[0][0]=1;
	for(i=0;i<6;i++){
		for(j=0;j<P;j++){
			for(k=0;k<13*P+1;k++){
				if(k+PDice[i]>=13*P+1)continue;
				dpP[j+1][k+PDice[i]]+=dpP[j][k];
				dpP[j+1][k+PDice[i]]%=mod;
			}
		}
	}
	
//for(i=0;i<13*P+1;i++)printf(i==0?"%lld":" %lld",dpP[P][i]);printf("\n");	
	
	// dpC[n][val]:n回の出目でvalになる組み合わせ
	dpC[0][0]=1;
	for(i=0;i<6;i++){
		for(j=0;j<C;j++){
			for(k=0;k<12*C+1;k++){
				if(k+CDice[i]>=12*C+1)continue;
				dpC[j+1][k+CDice[i]]+=dpC[j][k];
				dpC[j+1][k+CDice[i]]%=mod;
			}
		}
	}
//for(i=0;i<12*C+1;i++)printf(i==0?"%lld":" %lld",dpC[C][i]);printf("\n");	
	
	// P,C個の組み合わせ：1回振って出る出目の組み合わせ
	int MaxLen=13*P+12*C;
	Long *Throw=(Long *)malloc((MaxLen+1)*sizeof(Long));
	for(i=0;i<MaxLen+1;i++)Throw[i]=0;
	for(i=0;i<=13*P;i++){
		for(j=0;j<=12*C;j++){
			Throw[i+j]+=dpP[P][i]*dpC[C][j];
			Throw[i+j]%=mod;
		}
	}
//for(i=0;i<MaxLen+1;i++)printf(i==0?"%lld":" %lld",Throw[i]);printf("\n");	
//printf("MaxLen=%d\n",MaxLen);

	// C[k]をk番目のマスに来る組み合わせとして、0番目のマスからN-1番目のマスまで順次サイコロを振っていく様子を考える。
	// 　・kマスからk+tマスに動く組み合わせは C[k]*Throw[t] だけあるので
	// 　　kマスでサイコロを振ると、C[k+j] (j=1,2,…,13*P+12*C)にC[k]*Throw[j]だけ足されていく。
	// 　・C[0]==1
	// 
	// 　(簡潔化のため出目の最大値＝３、Throw[1]=a,Throw[2]=b,Throw[3]=c　とし、N=5とすると
	// 　 
	// 　	Turn            0      1       2         3              4              5              6             7 (マス)
	// 	0	C[*]    1(=C0) 
	// 	1	C[*]           C0*a    C0*b      C0*c
	// 			       (=C1)
	// 	2	C[*]                   C0*b+C1*a C0*c+C1*b	C1*c
	// 		                       (=C2)
	// 	3	C[*]                             C0*c+C1*b+C2*a C1*c+C2*b      C2*c
	//		                                 (=C3)
	// 	4	C[*]                                            C1*c+C2*b+C3*a C2*c+C3*b      C3*c
	//	                                                        (=C4)
	// 	5	C[*]                                                           C2*c+C3*b+C4*a C3*c+C4*b     C4*c
	// 
	// 	この時点で全ての場合においてN>=5にゴールしているので、ここで和を取る。(C2*c+C3*b+C4*a + C3*c+C4*b + C4*c)
	// 
	// 　・ここで係数だけみると、 多項式 T^7 を 多項式 T^3-(a*T^2+b*T^1+c*T^0) で筆算で割り算しているのと同じという事がわかる。
	// 　　（最後に余りの係数の総和をとる）
	// 　・ということで、元の問題は 多項式 T^(N+(出目の最大値)-1) を 多項式 ΣThrow[k]*T^k で割って、余りを求めればよい。
	
	
	// kitamasa(O(d^2 Log N)）
	Long rel[MaxLen];
	for(i=0;i<MaxLen;i++)rel[i]=Throw[MaxLen-i];
	
	// usage:ak=rel[0]*a0+...+rel[k-1]*a(k-1);
	//       T^k=rel[0]*1+rel[1]*T^1+...+rel[k-1]*T^(k-1);
	
	ModPolynomial_m_init(rel,mod,MaxLen);
	Long *coef;
	int coefLen=0;
	coef=Kitamasa_CalcModPolyT(N+MaxLen-1,&coefLen);
	
	Long ret=0;
	for(i=0;i<coefLen;i++){
		ret+=1*coef[i];
		while(ret>mod)ret-=mod;
	}
	
	printf("%lld\n",ret);
	
	return 0;
}
0