結果

問題 No.213 素数サイコロと合成数サイコロ (3-Easy)
ユーザー yaoshimaxyaoshimax
提出日時 2015-05-24 22:50:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 505 ms / 3,000 ms
コード長 2,240 bytes
コンパイル時間 533 ms
コンパイル使用メモリ 60,348 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 08:08:13
合計ジャッジ時間 1,628 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
   long long N;
   int P,C;
   cin>>N>>P>>C;
   int mod=1000000007;
   int dp[130][P+1][6];
   int dp2[130][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));
   dp[0][0][0]=1;
   for( int i=1 ; i<=P; i++ )for( int j=0;j<130;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]+=dp[j-pdice[k]][i-1][l];
      }
   }
   for(int i=0;i<130;i++){
      for(int k=0; k<6; k++){
         dp2[i][0][0]+=dp[i][P][k];
      }
   }
   for( int i=1 ; i<=C; i++ )for( int j=0;j<130;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]+=dp2[j-cdice[k]][i-1][l];
      }
   }
   int pattern[130];
   memset(pattern,0,sizeof(pattern));
   int aSize=0;
   for(int i=0;i<130;i++){
      for( int k=0;k<6;k++){
         pattern[i]+=dp2[i][C][k];
      }
      //cout << i<<","<<pattern[i]<<endl;
      if(pattern[i]>0) aSize=max(aSize,i);
   }
   int A[aSize][aSize];
   int V[aSize];
   memset(A,0,sizeof(A));
   memset(V,0,sizeof(V));
   V[0]=1;
   for( int i=0; i<aSize-1; i++){
      A[i][i+1]=1;
   }
   for( int i=1; i<=aSize; i++){
      A[i-1][0]=pattern[i];
   }
   /*
   for( int i = 0 ; i <aSize; i++){
      for( int j = 0 ; j < aSize;j++){
         cout << A[i][j]<<" ";
      }
      cout << endl;
   }
   */
   int V2[aSize];
   int A2[aSize][aSize];
   while(N>0){
      if( N%2==1 ){
         memset(V2,0,sizeof(V2));
         for( int i = 0 ; i<aSize ;i++ ){
            for( int j = 0 ; j < aSize ; j++ ){
               V2[i]=(V2[i]+A[i][j]*1LL*V[j])%mod;
            }
         }
         memcpy(V,V2,sizeof(V2));
      }
      memset(A2,0,sizeof(A2));
      for( int i=0;i<aSize;i++){
         for(int j=0;j<aSize;j++){
            for(int k=0;k<aSize;k++){
               A2[i][j]=(A2[i][j]+A[i][k]*1LL*A[k][j])%mod;
            }
         }
      }
      memcpy(A,A2,sizeof(A2));
      N/=2;
   }
   long long ans=0;
   for( int i = 0 ; i < aSize; i++){
      ans+=V[i];
      ans%=mod;
   }
   cout << ans << endl;

   return 0;
}
0