Submission #621204
Source Code Expand
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <fstream> #include <queue> #include <complex> #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double using namespace std; #define MAX_N 255 #define MAX_X 255 #define mod 1000000007 int N, X; string S; //dp[pos][nico_counting_cnt][nico_count][2] LL dp[MAX_N][MAX_N][MAX_X][2]; int main(){ cin >> N >> X; cin >> S; X--; dp[0][0][0][0] = 1; for(int pos = 0; pos < N; pos++){ for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){ for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){ for(int flag2 = 0; flag2 < 2; flag2++){ if(dp[pos][nico_counting_cnt][nico_cnt][flag2] == 0) continue; //直前の文字が2であったとき if(flag2){ if(S[pos] == '?'){ //?に5を割り当てるとニコニコ文字列になる if(nico_counting_cnt + 1 + nico_cnt <= X){ dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1]; dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] %= mod; } //?に5以外の数字を割り当てる //2を割り当てない場合 dp[pos+1][0][nico_cnt][0] += (LL)8*dp[pos][nico_counting_cnt][nico_cnt][1]; dp[pos+1][0][nico_cnt][0] %= mod; //2を割り当てる場合 dp[pos+1][0][nico_cnt][1] += dp[pos][nico_counting_cnt][nico_cnt][1]; dp[pos+1][0][nico_cnt][1] %= mod; } else if(S[pos] == '2'){ dp[pos+1][0][nico_cnt][1] += dp[pos][nico_counting_cnt][nico_cnt][1]; dp[pos+1][0][nico_cnt][1] %= mod; } else if(S[pos] == '5'){ if(nico_counting_cnt + 1 + nico_cnt <= X){ dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1]; dp[pos+1][nico_counting_cnt + 1][nico_counting_cnt + 1 + nico_cnt][0] %= mod; } } else{ dp[pos+1][0][nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][1]; dp[pos+1][0][nico_cnt][0] %= mod; } } //直前の文字が2以外であった時 else{ if(S[pos] == '?'){ //?に2を割り当てればnico_countingを継続した状態を引き継げる dp[pos+1][nico_counting_cnt][nico_cnt][1] += dp[pos][nico_counting_cnt][nico_cnt][0]; dp[pos+1][nico_counting_cnt][nico_cnt][1] %= mod; //?に2以外を割り当てる場合 dp[pos+1][0][nico_cnt][0] += (LL)9*dp[pos][nico_counting_cnt][nico_cnt][0]; dp[pos+1][0][nico_cnt][0] %= mod; } else if(S[pos] == '2'){ dp[pos+1][nico_counting_cnt][nico_cnt][1] += dp[pos][nico_counting_cnt][nico_cnt][0]; dp[pos+1][nico_counting_cnt][nico_cnt][1] %= mod; } else{ dp[pos+1][0][nico_cnt][0] += dp[pos][nico_counting_cnt][nico_cnt][0]; dp[pos+1][0][nico_cnt][0] %= mod; } } } } } } LL ans = 1; for(int i = 0; i < N; i++){ if(S[i] == '?'){ ans *= 10; ans %= mod; } } LL tmp = 0; for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){ for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){ for(int flag2 = 0; flag2 < 2; flag2++){ if(dp[N][nico_counting_cnt][nico_cnt][flag2] > 0){ tmp += dp[N][nico_counting_cnt][nico_cnt][flag2]; tmp %= mod; } } } } ans -= tmp; if(ans < 0) ans += mod; cout << ans%mod << endl; /* for(int i = 0; i <= N; i++){ for(int nico_counting_cnt = 0; nico_counting_cnt <= X; nico_counting_cnt++){ for(int nico_cnt = 0; nico_cnt <= X; nico_cnt++){ for(int flag2 = 0; flag2 < 2; flag2++){ fprintf(stderr, "(i,nico_counting_cnt, nico_cnt, flag2),(%d,%d,%d,%d) := %lld\n", i, nico_counting_cnt, nico_cnt, flag2, dp[i][nico_counting_cnt][nico_cnt][flag2]); } } } } */ return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - ニコニコ文字列2 |
User | takoshi |
Language | C++ (G++ 4.6.4) |
Score | 20 |
Code Size | 4658 Byte |
Status | AC |
Exec Time | 340 ms |
Memory | 22064 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 20 / 20 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | 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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 26 ms | 1044 KB |
sample_02.txt | AC | 27 ms | 1076 KB |
subtask1_01.txt | AC | 25 ms | 956 KB |
subtask1_02.txt | AC | 24 ms | 1052 KB |
subtask1_03.txt | AC | 29 ms | 1052 KB |
subtask1_04.txt | AC | 26 ms | 1048 KB |
subtask1_05.txt | AC | 33 ms | 1724 KB |
subtask1_06.txt | AC | 67 ms | 1908 KB |
subtask1_07.txt | AC | 41 ms | 1452 KB |
subtask1_08.txt | AC | 91 ms | 4784 KB |
subtask1_09.txt | AC | 47 ms | 2864 KB |
subtask1_10.txt | AC | 44 ms | 2096 KB |
subtask1_11.txt | AC | 40 ms | 2096 KB |
subtask1_12.txt | AC | 276 ms | 2352 KB |
subtask1_13.txt | AC | 36 ms | 1844 KB |
subtask1_14.txt | AC | 279 ms | 3116 KB |
subtask1_15.txt | AC | 298 ms | 10668 KB |
subtask1_16.txt | AC | 298 ms | 9900 KB |
subtask1_17.txt | AC | 340 ms | 22064 KB |
subtask1_18.txt | AC | 278 ms | 1844 KB |
subtask1_19.txt | AC | 338 ms | 20540 KB |
subtask1_20.txt | AC | 301 ms | 10292 KB |
subtask1_21.txt | AC | 27 ms | 1044 KB |
subtask1_22.txt | AC | 26 ms | 944 KB |