結果
問題 | No.213 素数サイコロと合成数サイコロ (3-Easy) |
ユーザー | latte0119 |
提出日時 | 2016-05-25 10:03:15 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 922 ms / 3,000 ms |
コード長 | 1,988 bytes |
コンパイル時間 | 1,748 ms |
コンパイル使用メモリ | 166,924 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-07 14:00:32 |
合計ジャッジ時間 | 4,706 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 845 ms
5,248 KB |
testcase_01 | AC | 922 ms
5,248 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long const int mod=1000000007; const int ps[]={2,3,5,7,11,13}; const int cs[]={4,6,8,9,10,12}; typedef vector<int>vec; typedef vector<vec>mat; mat mul(mat A,mat B){ mat C(A.size(),vec(B[0].size())); for(int i=0;i<C.size();i++){ for(int j=0;j<C[0].size();j++){ for(int k=0;k<A[0].size();k++){ C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod; } } } return C; } mat matpow(mat A,int m){ mat B(A.size(),vec(A.size())); for(int i=0;i<B.size();i++)B[i][i]=1; while(m){ if(m&1)B=mul(B,A); A=mul(A,A); m>>=1; } return B; } const int SIZE=130; int N,P,C; int dp[10][10][200]; int f[200]; signed main(){ cin>>N>>P>>C; dp[0][0][0]=1; for(int i=0;i<6;i++){ for(int j=0;j<=P;j++){ for(int k=0;k<200;k++){ for(int l=0;l+j<=P;l++){ if(k+ps[i]*l<200)dp[i+1][j+l][k+ps[i]*l]=(dp[i+1][j+l][k+ps[i]*l]+dp[i][j][k])%mod; } } } } for(int i=0;i<10;i++){ for(int j=0;j<10;j++){ for(int k=0;k<200;k++){ if(i==0&&j==0)dp[0][0][k]=dp[6][P][k]; else dp[i][j][k]=0; } } } for(int i=0;i<6;i++){ for(int j=0;j<=C;j++){ for(int k=0;k<200;k++){ for(int l=0;l+j<=C;l++){ if(k+cs[i]*l<200)dp[i+1][j+l][k+cs[i]*l]=(dp[i+1][j+l][k+cs[i]*l]+dp[i][j][k])%mod; } } } } for(int i=0;i<200;i++)f[i]=dp[6][C][i]; mat A(SIZE,vec(SIZE)); mat X(SIZE,vec(1)); X[0][0]=1; for(int i=0;i<SIZE-1;i++){ A[i+1][i]=1; A[0][i]=f[i+1]; } X=mul(matpow(A,N-1),X); int ans=0; for(int i=1;i<SIZE;i++){ for(int j=0;j<i;j++){ ans=(ans+X[j][0]*f[i])%mod; } } cout<<ans<<endl; return 0; }