結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー kuuso1kuuso1
提出日時 2015-08-11 17:21:31
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 12,902 bytes
コンパイル時間 900 ms
コンパイル使用メモリ 115,428 KB
実行使用メモリ 27,480 KB
最終ジャッジ日時 2024-07-18 06:44:09
合計ジャッジ時間 11,273 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,067 ms
19,968 KB
testcase_01 AC 2,818 ms
27,480 KB
testcase_02 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int[] PDice=new int[]{2,3,5,7,11,13};
		int[] CDice=new int[]{4,6,8,9,10,12};
		
		int mod=(int)1e9+7;
		
		// dpP[n][val]:n回の出目でvalになる組み合わせ
		int[][] dpP=new int[P+1][];
		for(int i=0;i<=P;i++){
			dpP[i]=new int[13*P+1];
		}
		dpP[0][0]=1;
		for(int i=0;i<PDice.Length;i++){
			for(int j=0;j<P;j++){
				for(int k=0;k<dpP[j].Length;k++){
					if(k+PDice[i]>=dpP[j+1].Length)continue;
					dpP[j+1][k+PDice[i]]+=dpP[j][k];
					dpP[j+1][k+PDice[i]]%=mod;
				}
			}
		}
//Console.WriteLine(String.Join(" ",dpP[P]));
		// dpC[n][val]:n回の出目でvalになる組み合わせ
		int[][] dpC=new int[C+1][];
		for(int i=0;i<=C;i++){
			dpC[i]=new int[12*C+1];
		}
		dpC[0][0]=1;
		for(int i=0;i<CDice.Length;i++){
			for(int j=0;j<C;j++){
				for(int k=0;k<dpC[j].Length;k++){
					if(k+CDice[i]>=dpC[j+1].Length)continue;
					dpC[j+1][k+CDice[i]]+=dpC[j][k];
					dpC[j+1][k+CDice[i]]%=mod;
				}
			}
		}
//Console.WriteLine(String.Join(" ",dpC[C]));
		
		// P,C個の組み合わせ:1回振って出る出目の組み合わせ
		int MaxLen=13*P+12*C;
		long[] Throw=new long[MaxLen+1];
		for(int i=0;i<=13*P;i++){
			for(int j=0;j<=12*C;j++){
				Throw[i+j]+=dpP[P][i]*dpC[C][j];
				Throw[i+j]%=mod;
			}
		}
		
//Console.WriteLine(String.Join(" ",Throw));
//Console.WriteLine("MaxLen={0}",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
		// 
		//  (簡潔化のため出目の最大値=3、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=new long[MaxLen];
		for(int i=0;i<MaxLen;i++)rel[i]=Throw[i+1];
		Array.Reverse(rel);
		// 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);
		var Kitamasa=new ModPolynomial_m(rel,mod);
		
		
//for(int i=0;i<30;i++)Console.WriteLine(i+":"+String.Join(" ",Kitamasa.CalcModPolyT(i))+":"+Kitamasa.CalcModPolyT(i).Sum());
		long[] coef=Kitamasa.CalcModPolyT(N+MaxLen-1);
		long ret=0;
		for(int i=0;i<coef.Length;i++){
			ret+=1*coef[i];
			while(ret>mod)ret-=mod;
		}
		Console.WriteLine(ret);
		
		
	}
	long N;
	int P,C;
	public Sol(){
		var ss=rsa();
		N=long.Parse(ss[0]);
		P=int.Parse(ss[1]);
		C=int.Parse(ss[2]);
	}




	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}


class ModPolynomial_m{
	//Kitamasa method (naive convolution/naive reduction);
	int K;
	long[] Rel;
	long mod;
	
	public ModPolynomial_m(long[] rel,long mod_){
		// 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);
		Rel=new long[rel.Length];
		K=Rel.Length;
		for(int i=0;i<K;i++)Rel[i]=rel[i];
		
		mod=mod_;
	}
	
	public long[] Convolution_m(long[] a,long[] b){
		// calc. a*b (convolution) naive
		int L=a.Length+b.Length-1;
		long[] ret=new long[L];
		for(int i=0;i<a.Length;i++){
			if(a[i]==0)continue;
			for(int j=0;j<b.Length;j++){
				if(b[j]==0)continue;
				ret[i+j]+=a[i]*b[j];
				if(ret[i+j]>mod)ret[i+j]%=mod;
			}
		}
		return ret;
	}
	
	public long[] Convolution_fmt(long[] a,long[] b){
		// calc. a*b (convolution) naive
		int[] aa=Array.ConvertAll(a,x=>(int)x);
		int[] ba=Array.ConvertAll(b,x=>(int)x);
		
		int[][] mab=new int[3][];
		ConvolutionMod[] cmd=new ConvolutionMod[3];
		int[] md=new int[]{0xA000001,0x1C000001,0x23800001};
		for(int i=0;i<3;i++){
			cmd[i]=new ConvolutionMod();
			mab[i]=cmd[i].Calc_FMT_CT(aa,ba,md[i]);
		}
		long[] ret=new long[aa.Length+ba.Length+1];
		for(int i=0;i<ret.Length;i++){
			ret[i]=Garner.CRT_min(md,new int[]{mab[0][i],mab[1][i],mab[2][i]})%mod;
		}
		return ret;
	}
	
	
	
	
	
	public long[] Reduction_m(long[] a){
		// reduce with Relation a(k)=rel[0]*a0+...+rel[k-1]*a(k-1);
		if(a.Length<=K)return a;
		int N=a.Length;
		//long[] ret0=(long[])a.Clone();
		long[] ret0=new long[a.Length];
		for(int i=0;i<a.Length;i++)ret0[i]=a[i];
		
		// longer than K part
		for(int i=N-1;i>=K;i--){
			if(ret0[i]==0)continue;
			for(int 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=new long[K];
		for(int i=0;i<K;i++)ret[i]=ret0[i];
		return ret;
	}
	
	public long[] CalcModPolyT(long k){
		// calc T^k mod Rel, return the coef.
		// b7=b(1+2+4)=b1*b2*b4 etc.
		long[] ret=new long[]{1};//b0
		long[] x=new long[]{0,1};//b1
		
		while(k>0){
			if((k&1)==1){
				ret=Reduction_m( Convolution_m( ret,x ));
			}
			k>>=1;
			x=Reduction_m( Convolution_m( x,x ));
		}
		return ret;
	}
	
/*

b0:(a0,a1,a2)->a0	b0=(1,0,0);

b0:(a1,a2,a3)->a1
b1:(a0,a1,a2)->a1	b1=(0,1,0);

b0:(a2,a3,a4)->a2	
b1:(a1,a2,a3)->a2	
b2:(a0,a1,a2)->a2	b2=(0,0,1);

b0:(a3,a4,a5)->a3	
b1:(a2,a3,a4)->a3	
b2:(a1,a2,a3)->a3	
b3:(a0,a1,a2)->a3	b3=(0,0,0,1)=(1,1,1)	<=> a3=a2+a1+a0; <=> t^3 mod t^3-t^2-t^1-1 = t^2+t^1+1

b0:(a4,a5,a6)->a4	
b1:(a3,a4,a5)->a4	
b2:(a2,a3,a4)->a4	
b3:(a1,a2,a3)->a4	
b4:(a0,a1,a2)->a4	b4=(0.0,0,0,1)=(0,1,1,1)=(1,2,2) <=> a4=a1+a2+a3=a0+2*a1+2*a2  <=> t^4 mod t^3-t^2-t^1-1 == t^3+t^2+t^1 == 2*t^2+2*t^1+1

b(x+y)=b(1+...+1+1+...+1)=b1*...*b1*b1*...*b1=b(1+...+1)*b(1+...+1)=bx*by

*/

}

class Garner{
	public static long CRT_min(int[] md,int[] coef){
		//http://www.csee.umbc.edu/~lomonaco/s08/441/handouts/Garner-Alg-Example.pdf
		if(md.Length==1)return coef[0];
		long[] v=new long[md.Length];
		v[0]=coef[0];
		long sum=v[0];
		long ml=1;
		for(int i=1;i<md.Length;i++){
			ml*=md[i-1];
			//sum%md[i]+v[i]*ml==coef[i];
			v[i]=(ModInv(ml,md[i])*(md[i]+coef[i]-sum%md[i]))%md[i];
			sum+=v[i]*ml;
		}
		
		return sum;
	}
	static long ModInv(long x,long mod){
		//拡張ユークリッドの互除法でmod逆元を求める
		//ax + mod * y = 1 で mod取れば ax = 1 になるから xがaの逆元になる
		//逆元が存在しない→0を返す。
		long a=0,b=0,c=0;
		if(x==0)return 0;
		if(x>=mod)x%=mod;
		ExtGCD(x,mod,ref a,ref b,ref c);
		if(c!=1)return 0;
		return ((a+mod)%mod);
	}
	
	static void ExtGCD(long x,long y,ref long a,ref long b,ref long c){
		long r0=x;long r1=y;
		long a0=1;long a1=0;
		long b0=0;long b1=1;
		long q1,r2,a2,b2;
		while(r1>0){
			q1=r0/r1;
			r2=r0%r1;
			a2=a0-q1*a1;
			b2=b0-q1*b1;
			r0=r1;r1=r2;
			a0=a1;a1=a2;
			b0=b1;b1=b2;
		}
		c=r0;
		a=a0;
		b=b0;
	}
	
}



class ConvolutionMod{
	//use in instance
	int N;
	int mod;
	
	public int[] Calc_FMT_CT(int[] A_,int[] B_,int mod_,int n_=0){
		//Cooley-Tukey 
		
		int nn=1;
		while(nn<(A_.Length-1+B_.Length-1+1))nn<<=1;
		N=n_==0?nn:n_;
		mod=mod_;//mod: (Power Of 2, >=N)*m+1 (=> MM=(mod-1)/N, 3^M:primitive N root in mod)
		
		int[] A=new int[N];
		for(int i=0;i<A_.Length;i++)A[i]=A_[i];
		int[] B=new int[N];
		for(int i=0;i<B_.Length;i++)B[i]=B_[i];
		
		FMT_CT(ref A,false);//in-Place
		FMT_CT(ref B,false);//in-Place
		
		int[] AB=new int[N];
		for(int i=0;i<N;i++)AB[i]=(int)(((long)A[i]*(long)B[i])%(long)mod);
		
		FMT_CT(ref AB,true);
		
		return AB;
		
	}
	
	
	void BitRev(ref int[] a){
		int i=0;
		int tmp;
		int n=a.Length;//Power of 2.
		for(int j=1;j<n-1;j++){
			for(int k=n>>1;k>(i^=k);k>>=1);
			if(j<i){
				tmp=a[j];a[j]=a[i];a[i]=tmp;
			}
		}
	}
	
	void FMT_CT(ref int[] a,bool inv){
		
		BitRev(ref a);
		int m=0;
		int k=0;
		int n=a.Length;
		int w,x;
		int sig=inv?-1:1;
		
		for(int mh=1;(m=(mh<<1))<=n;mh=m){
			int irev=0;
			for(int i=0;i<n;i+=m){
				w=cExp(sig,irev,n);
				for(k=n>>2;k>(irev^=k);k>>=1);
				for(int j=i;j<mh+i;j++){
					k=j+mh;
					x=mod+a[j]-a[k];
					
					a[j]+=a[k];if(a[j]>=mod)a[j]-=mod;
					
					a[k]=(int)(((long)w*(long)x)%(long)mod);
				}
			}
		}
		if(inv){
			for(int i=0;i<n;i++){
				a[i]= (int)((long)a[i]*(long)ModInv(n)%(long)mod);
			}
		}
		
	}
	
	
	public int[] Calc_FMT_Stkhm(int[] A_,int[] B_,int mod_,int n_=0){
		//Stockham
		int nn=1;
		while(nn<(A_.Length-1+B_.Length-1+1))nn<<=1;
		N=n_==0?nn:n_;
		mod=mod_;//mod: (Power Of 2, >=N)*m+1 (=> MM=(mod-1)/N, 3^M:primitive N root in mod)

		int[] A=new int[N];
		for(int i=0;i<A_.Length;i++)A[i]=A_[i];
		int[] B=new int[N];
		for(int i=0;i<B_.Length;i++)B[i]=B_[i];
		
		FMT_Stkhm(ref A,false);//in-Place
		FMT_Stkhm(ref B,false);//in-Place
		
		int[] AB=new int[N];
		for(int i=0;i<N;i++)AB[i]=(int)(((long)A[i]*(long)B[i])%(long)mod);
		
		FMT_Stkhm(ref AB,true);
		
		return AB;
		
	}
	
	void FMT_Stkhm(ref int[] a,bool inv){
		
		int n=a.Length;
		int[] buf=new int[n];
		int x;
		int sig=inv?-1:1;
		
		int nStride=n;
		for(int Stride=1;Stride<n;Stride<<=1){
			nStride>>=1;
			for(int i=0;i<nStride;i++){
				for(int j=0;j<Stride;j++){
					x=(int)((long)a[Stride*i+n/2+j]*(long)cExp(sig,nStride*j,n)%(long)mod);
					buf[2*Stride*i+j]=a[Stride*i+j]+x;if(buf[2*Stride*i+j]>=mod)buf[2*Stride*i+j]-=mod;
					buf[2*Stride*i+j+Stride]=mod+a[Stride*i+j]-x;if(buf[2*Stride*i+j+Stride]>=mod)buf[2*Stride*i+j+Stride]-=mod;
				}
			}
			for(int i=0;i<n;i++)a[i]=buf[i];
		}
		if(inv){
			for(int i=0;i<n;i++){
				a[i]= (int)((long)a[i]*(long)ModInv(n)%(long)mod);
			}
		}
		
	}
	
	
	
	
	
	int[] PowTable;
	bool initSC=false;
	
	int cExp(int sig,int num,int den){
		if(!initSC)InitSC();
		if(N>den){
			int x=TrailingZerosOf(N)-TrailingZerosOf(den);
			num<<=x;den<<=x;
		}
		return PowTable[sig==1?num:(N-num)%N];
	}
	
	public void InitSC(){
		PowTable=new int[N];
		PowTable[0]=1;
		
		int m=(mod-1)/N;
		
		long xx=3;
		long x=1;
		while(m>0){
			if((m&1)>0){
				x*=xx;
				if(x>mod)x%=mod;
			}
			xx*=xx;
			if(xx>mod)xx%=mod;
			m>>=1;
		}
		
		PowTable[1]=(int)x;
		
		for(int i=2;i<N;i++){
			x*=PowTable[1];
			if(x>mod)x%=mod;
			PowTable[i]=(int)x;
		}
		initSC=true;
	}
	
	
	bool initTZ=false;
	int[] table;
	
	public int TrailingZerosOf( long x ){
		if(x==0)return 64;
		if(!initTZ)InitTZ();
		ulong y=(ulong)(x&-x);
		int i=(int)((y*0x03F566ED27179461UL)>>58);
		return table[i];
	}
	public void InitTZ(){
		table=new int[64];
		ulong hash = 0x03F566ED27179461UL;
		for(int i=0;i<64;i++){
			table[hash>>58]=i;
			hash<<=1;
		}
		initTZ=true;
	}
	
	
	public int ModInv(long x){
		//拡張ユークリッドの互除法でmod逆元を求める
		//ax + mod * y = 1 で mod取れば ax = 1 になるから xがaの逆元になる
		//逆元が存在しない→0を返す。
		long a=0,b=0,c=0;
		if(x==0)return 0;
		ExtGCD(x,mod,ref a,ref b,ref c);
		if(c!=1)return 0;
		return (int)((a+mod)%mod);
	}
	
	public static void ExtGCD(long x,long y,ref long a,ref long b,ref long c){
		long r0=x;long r1=y;
		long a0=1;long a1=0;
		long b0=0;long b1=1;
		long q1,r2,a2,b2;
		while(r1>0){
			q1=r0/r1;
			r2=r0%r1;
			a2=a0-q1*a1;
			b2=b0-q1*b1;
			r0=r1;r1=r2;
			a0=a1;a1=a2;
			b0=b1;b1=b2;
		}
		c=r0;
		a=a0;
		b=b0;
	}
	
	
	
	
}
0