結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー yaoshimaxyaoshimax
提出日時 2015-06-24 01:59:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 846 ms / 3,000 ms
コード長 4,445 bytes
コンパイル時間 547 ms
コンパイル使用メモリ 70,516 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-07-07 17:18:43
合計ジャッジ時間 3,711 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 605 ms
6,816 KB
testcase_01 AC 783 ms
6,940 KB
testcase_02 AC 846 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
class Kitamasa{
   private:
      vector<long long> C; // a[n+1] = C[0] a[n] + C[1] a[n-1]+...C[S-1] a[n-S+1] (n=0,1,...)
      int mod;
      long long lim;
   public:
      Kitamasa(vector<long long> p){
         C=p;mod=1000000007,lim=1LL<<60;
      }
      vector<long long> mul(vector<long long>& u, vector<long long>& v){
         // a[x] = (u[S-1] a[S-1] + u[S-2] a[S-2] +, ... + u[0] a[0])
         // a[y] = (v[S-1] a[S-1] + v[S-2] a[S-2] +, ... + v[0] a[0])
         // our purpose is to calculate w such that
         // a[x+y] = (w[S-1] a[S-1] + w[S-2] a[S-2] +, ... + w[0] a[0])  
         // a[x+y] = (u[S-1]a[y+S-1]+u[S-2]a[y+S-2]+...+u[0]a[y])     
         //        = (u[S-1](v[S-1]a[2S-2]+v[S-2]a[2S-3]+...+v[0]a[S-1])
         //          +u[S-2](v[S-1]a[2S-3]+v[S-2]a[2S-4]+...+v[0]a[S-2])
         //          +...)
         //        = sum(u[i]v[j]a[k]) where 0<=i,j<=S-1, i+j=k
         int S=u.size();
         vector<long long> ret(2*S-1,0);
         for( int i = 0 ; i < S; i++){
            for( int j=0;j<S;j++){
               ret[i+j]+=u[i]*v[j];
               if(ret[i+j]>lim)ret[i+j]%=mod;
            }
         }
         // now a[x+y]=ret[2S-2] a[2S-2]+ret[2S-3] a[2S-3]+...ret[0] a[0].

         // move ret[S+i] into ret[S+i-1]... (i=0,1,2,...,S-1)
         // the key concept is, ret[S+i]a[S+i] = ret[S+i](C[0]a[S+i-1]+C[1]a[S+i-2]+....C[S-1]a[i])
         for( int i = 2*S-2; i>=S; i--){
            ret[i]%=mod;
            for( int j = 0 ; j < S; j++){
               ret[i-1-j]+=ret[i]*C[j];
               if(ret[i-1-j]>lim) ret[i-1-j]%=mod;
            }
         }
         for(int i=0;i <S; i++ )ret[i]%=mod;
         ret.resize(S);
         return ret;
      }
};

int main(){
   long long N;
   int P,C;
   cin>>N>>P>>C;
   int T=P*13+C*12+1;
   int dp[T][P+1][6];
   int dp2[T][C+1][6];
   int pdice[]={2,3,5,7,11,13};
   int cdice[]={4,6,8,9,10,12};
   memset(dp,0,sizeof(dp));
   memset(dp2,0,sizeof(dp2));
   int mod=1000000007;
   dp[0][0][0]=1;
   for( int i=1 ; i<=P; i++ )for( int j=0;j<T;j++) for( int k=0; k<6; k++ ){//fill dp[j][i][k]
      for( int l=0;l<=k; l++){
         if(j-pdice[k]>=0)dp[j][i][k]=(1LL*dp[j][i][k]+dp[j-pdice[k]][i-1][l])%mod;
      }
   }
   for(int i=0;i<T;i++){
      for(int k=0; k<6; k++){
         dp2[i][0][0]=(1LL*dp2[i][0][0]+dp[i][P][k])%mod;
      }
   }
   for( int i=1 ; i<=C; i++ )for( int j=0;j<T;j++) for( int k=0; k<6; k++ ){//fill dp2[j][i][k]
      for( int l=0;l<=k; l++){
         if(j-cdice[k]>=0)dp2[j][i][k]=(1LL*dp2[j][i][k]+dp2[j-cdice[k]][i-1][l])%mod;
      }
   }
   vector<long long> pattern(T,0);
   for(int i=0;i<T;i++){
      for( int k=0;k<6;k++){
         pattern[i]+=dp2[i][C][k];
         pattern[i]%=mod;
      }
   }
   int S=T-1;
   // a[n+1] = p[0] a[n] + p[1] a[n-1]+...p[S-1] a[n-S+1] (n>=0,p[i]=pattern[i+1])
   // initial value: a[0]=1,a[-1]=1,a[-2]=1,.... # to regard a[n] as num of the way to over n 
   // a[1] = p[0]a[0]+ p[1]a[-1]+....p[S-1]a[-S+1]  
   // let's denote coefficients as v[1]=(p[0],...,p[S-1])
   // a[2] = p[0]a[1]+ p[1]a[0]+....p[S-1]a[-S+2]
   //      = (p[1]+p[0]^2)a[0]+(p[2]+p[1]p[0])a[1]...(p[S-1]+p[S-2]p[0])a[-S+2]+p[S-1]a[-S+1]
   // this can be described as v[2]=(p[1]+p[0]^2,...,p[-S+2]+p[-S+1]p[0],p[S-1])
   // Now, let's calculate v[N] with initial value is a[0]=a[-1]=a[-2]=...=a[-S+1]=1
   // this can be regarded as calculate V[N+S-1] with initial value A[S-1]=...=A[0]=1
   // note that V[0]=v[-S+1]=(0,0,0,...,1), V[1]=(0,0,0,...,1,0);
   long long EXP=N+S-1;
   vector<long long> v(S,0);
   for( int i =0 ; i < S; i++ ){
      v[i]=pattern[i+1]%mod;
      //cout << v[i] <<", ";
   }
   //cout << endl;
   long long ans = 0;
   Kitamasa ktms(v);
   vector<long long> a(S,0);
   vector<long long> b(S,0);
   a[0]=1;
   b[1]=1;
   //cout << EXP << endl;
   while( EXP > 0 ){
      if( EXP%2==1 ){
         a=ktms.mul(a,b);
         /*
            cout << cnt<<": ";
            for( int i =0 ; i < S; i++ ){ cout << a[i]<<"+";}
            cout << endl;
            */
      }
      b=ktms.mul(b,b);
      /*
         cout << off<<": ";
         for( int i =0 ; i < S; i++ ){ cout << b[i]<<"+";}
         cout << endl;
         */
      EXP/=2;
   }
   for( int i = 0 ; i <S; i++ ){
      ans+=a[i];
      ans%=mod;
   }
   cout << ans << endl;
   return 0;
}
0