結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー kuuso1kuuso1
提出日時 2015-08-30 12:53:52
言語 C90
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 4,786 bytes
コンパイル時間 1,033 ms
コンパイル使用メモリ 28,196 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-25 19:47:22
合計ジャッジ時間 2,374 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

//kitamasa
int K;
Long Rel[8000];
int 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;
	
	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;
		}
	}
	return ret;
}

Long *Reduction_m(Long a[],int *aLen){
	// reduce with Relation a(k)=rel[0]*a0+...+rel[k-1]*a(k-1);
	if(*aLen<=K)return a;
	int N=*aLen;
	int i,j;
	//long[] ret0=(long[])a.Clone();
	Long ret0[*aLen];
	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];
	*aLen=K;
	return ret;
}


Long *Kitamasa_CalcModPolyT(Long k,int *len){
	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;
	
	while(k>0){
		if(k&1){
			ret=Reduction_m( Convolution_m( ret,x,&retLen,&xLen,&retLen ),&retLen);
		}
		k=(k>>1);
		x=Reduction_m( Convolution_m( x,x,&xLen,&xLen,&xLen ),&xLen);
	}
	*len=retLen;
	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=(int)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;
			}
		}
	}
	
	// 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;
			}
		}
	}
	
	// P,C個の組み合わせ：1回振って出る出目の組み合わせ
	int MaxLen=13*P+12*C;
	Long Throw[MaxLen+1];
	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;
		}
	}

	// 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