Submission #818366
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define fi first #define se second const ll mod=1e9+7; int N,X,Y,Z; int S; bool nx[1<<16][11]; ll dp[41][1<<16]; ll dfs(int now, int state) { if(dp[now][state]>=0) return dp[now][state]; if(now==N) return 1; ll ret=0; //次に選ぶ数 for(int i=1; i<=10; ++i) { if(nx[state][i]) { ret+=dfs(now+1, ((state<<i)+(1<<(i-1)))%(1<<S)); ret%=mod; } } return dp[now][state]=ret; } int main() { cin >>N >>X >>Y >>Z; S=X+Y+Z-1; //状態maskの時に,次の数iが来ていいかチェックしておく rep(mask,1<<S) { //直前の状態を復元 vector<int> b; int st=0; rep(i,S) { if(mask>>i&1) { b.pb(i-st+1); st=i+1; } } int B=b.size(); //jを次に選んだ時にXYZを含まないかチェック for(int i=1; i<=10; ++i) { bool ok=true; //直前から順番に見ていき貪欲に足していく int x=0,y=0,z=i; int bidx=0; while(bidx<B && z<Z) z+=b[bidx++]; while(bidx<B && y<Y) y+=b[bidx++]; while(bidx<B && x<X) x+=b[bidx++]; if(x==X && y==Y && z==Z) ok=false; nx[mask][i]=ok; } } //全体は10^N通り ll p10=1; rep(i,N) p10=(p10*10)%mod; memset(dp,-1,sizeof(dp)); //XYZを含まない数列の個数 ll r=dfs(0,0); //全体から引く ll ans=(p10-r+mod)%mod; cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Iroha and Haiku |
User | imulan |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1986 Byte |
Status | AC |
Exec Time | 510 ms |
Memory | 21888 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt |
All | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_max1.txt, subtask1_max2.txt, subtask1_max3.txt, subtask1_min1.txt, subtask1_min2.txt, subtask1_min3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 79 ms | 21888 KB |
subtask0_sample_02.txt | AC | 80 ms | 21888 KB |
subtask0_sample_03.txt | AC | 36 ms | 21248 KB |
subtask0_sample_04.txt | AC | 510 ms | 21888 KB |
subtask1_01.txt | AC | 35 ms | 21248 KB |
subtask1_02.txt | AC | 46 ms | 21248 KB |
subtask1_03.txt | AC | 37 ms | 21248 KB |
subtask1_04.txt | AC | 41 ms | 21248 KB |
subtask1_05.txt | AC | 37 ms | 21248 KB |
subtask1_06.txt | AC | 35 ms | 21248 KB |
subtask1_07.txt | AC | 39 ms | 21248 KB |
subtask1_08.txt | AC | 35 ms | 21248 KB |
subtask1_09.txt | AC | 37 ms | 21248 KB |
subtask1_10.txt | AC | 36 ms | 21248 KB |
subtask1_11.txt | AC | 39 ms | 21248 KB |
subtask1_12.txt | AC | 65 ms | 21376 KB |
subtask1_13.txt | AC | 45 ms | 21248 KB |
subtask1_14.txt | AC | 36 ms | 21248 KB |
subtask1_15.txt | AC | 62 ms | 21248 KB |
subtask1_16.txt | AC | 210 ms | 21632 KB |
subtask1_17.txt | AC | 76 ms | 21376 KB |
subtask1_18.txt | AC | 141 ms | 21376 KB |
subtask1_19.txt | AC | 88 ms | 21376 KB |
subtask1_20.txt | AC | 47 ms | 21248 KB |
subtask1_21.txt | AC | 133 ms | 21376 KB |
subtask1_22.txt | AC | 83 ms | 21376 KB |
subtask1_23.txt | AC | 76 ms | 21376 KB |
subtask1_24.txt | AC | 59 ms | 21248 KB |
subtask1_25.txt | AC | 83 ms | 21376 KB |
subtask1_max1.txt | AC | 508 ms | 21888 KB |
subtask1_max2.txt | AC | 479 ms | 21888 KB |
subtask1_max3.txt | AC | 257 ms | 21632 KB |
subtask1_min1.txt | AC | 35 ms | 21248 KB |
subtask1_min2.txt | AC | 35 ms | 21248 KB |
subtask1_min3.txt | AC | 78 ms | 21888 KB |