結果
| 問題 | No.214 素数サイコロと合成数サイコロ (3-Medium) |
| ユーザー |
 kuuso1
|
| 提出日時 | 2015-09-07 01:52:12 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,559 bytes |
| コンパイル時間 | 1,198 ms |
| コンパイル使用メモリ | 114,948 KB |
| 実行使用メモリ | 58,300 KB |
| 最終ジャッジ日時 | 2024-07-19 04:48:40 |
| 合計ジャッジ時間 | 12,165 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
コンパイルメッセージ
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;
using System.Diagnostics;
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
//
// (簡潔化のため出目の最大値＝３、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;
Stopwatch sw;
long ltime;
void swStart(){
sw=new Stopwatch();
sw.Start();
ltime=0;
}
void Etime(String s,bool write=true){
if(write)Console.WriteLine("{0}:\t{1}\t[ms]\tduration\t{2}\t[ms]",s,sw.ElapsedMilliseconds,sw.ElapsedMilliseconds-ltime);
ltime=sw.ElapsedMilliseconds;
}
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);
swStart();
Rel=new long[rel.Length];
K=Rel.Length;
for(int i=0;i<K;i++)Rel[i]=rel[i];
mod=mod_;
mInit(mod);
//Etime("constructor end");
}
public long[] Convolution_m(long[] a,long[] b){
// calc. a*b (convolution) naive
//Etime("Convolute start",false);
long lmN=mN;
long lmR2=mR2;
long lmxN=mxN;
//int t=0;
long lt=0;
//int s=0;
//long ls=0;
//long ab=0;
int ilmN=(int)lmN;
int imxN=(int)mxN;
int imod=(int)mod;
//Console.WriteLine("lmxN={0},lmN={1},lmR2={2}",lmxN,lmN,lmR2);
int L=a.Length+b.Length-1;
int[] ret=new int[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;
lt=(a[i]*b[j]+((a[i]*b[j]*lmxN)&0x3FFFFFFF)*lmN)>>30;
lt=lmR2*(lt<lmN?lt:lt-lmN);
lt=(lt+((lt*lmxN)&0x3FFFFFFF)*lmN)>>30;
ret[i+j]+=lt<lmN?(int)lt:(int)(lt-lmN);
//ret[i+j]+=(int)lt;
if(ret[i+j]>imod)ret[i+j]-=imod;
}
}
//Etime("Convolute end");
return Array.ConvertAll(ret,x=>(long)x);
}
public long[] Reduction_m(long[] a){
//Etime("Reduction start");
// 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];
//Etime("Reduction end");
return ret;
}
public long[] CalcModPolyT(long k){
//Etime("CalcModPoly start");
// 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){
//Console.WriteLine("k={0},retLen={1},ret={2}",k,ret.Length,String.Join(" ",ret));
if((k&1)==1){
ret=Reduction_m( Convolution_m( ret,x ));
}
k>>=1;
x=Reduction_m( Convolution_m( x,x ));
}
//Etime("CalcModPoly end");
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
*/
static long mN;//mod
static long mR;//coef
static long mxN;// xN*N=1 mod R;
static long mR2;// R*R mod N;
static long miR;// iR*R=1 mod N;
public static void mInit(long n){
mN=n;mR=1L<<30;
mR2=(mR*mR)%mN;
long c=1;
// iR * R + (-xN) * N = 1
ExtGCD(mR,mN,ref miR,ref mxN,ref c);
mxN*=-1;while(mxN<0)mxN+=mR;
}
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;
}
}