結果
問題 | No.214 素数サイコロと合成数サイコロ (3-Medium) |
ユーザー | kuuso1 |
提出日時 | 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.
ソースコード
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; } }