結果
問題 | No.260 世界のなんとか3 |
ユーザー | alumina_8 |
提出日時 | 2019-03-29 15:03:17 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 2,182 bytes |
コンパイル時間 | 634 ms |
コンパイル使用メモリ | 83,644 KB |
実行使用メモリ | 19,852 KB |
最終ジャッジ日時 | 2023-08-20 12:08:23 |
合計ジャッジ時間 | 2,860 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,496 KB |
testcase_01 | AC | 2 ms
5,536 KB |
testcase_02 | AC | 2 ms
5,492 KB |
testcase_03 | AC | 100 ms
18,560 KB |
testcase_04 | AC | 100 ms
19,668 KB |
testcase_05 | AC | 21 ms
7,600 KB |
testcase_06 | AC | 14 ms
6,552 KB |
testcase_07 | AC | 68 ms
14,112 KB |
testcase_08 | AC | 47 ms
10,576 KB |
testcase_09 | AC | 27 ms
8,304 KB |
testcase_10 | AC | 76 ms
15,244 KB |
testcase_11 | AC | 73 ms
15,048 KB |
testcase_12 | AC | 45 ms
10,216 KB |
testcase_13 | AC | 14 ms
6,388 KB |
testcase_14 | AC | 68 ms
14,800 KB |
testcase_15 | AC | 19 ms
7,100 KB |
testcase_16 | AC | 57 ms
12,124 KB |
testcase_17 | AC | 47 ms
11,940 KB |
testcase_18 | AC | 43 ms
10,228 KB |
testcase_19 | AC | 58 ms
12,604 KB |
testcase_20 | AC | 41 ms
10,500 KB |
testcase_21 | AC | 35 ms
8,736 KB |
testcase_22 | AC | 66 ms
14,896 KB |
testcase_23 | AC | 8 ms
5,932 KB |
testcase_24 | AC | 52 ms
12,324 KB |
testcase_25 | AC | 62 ms
11,196 KB |
testcase_26 | AC | 39 ms
11,624 KB |
testcase_27 | AC | 2 ms
5,476 KB |
testcase_28 | AC | 101 ms
19,852 KB |
testcase_29 | AC | 121 ms
18,924 KB |
ソースコード
#include <iostream> #include <string> constexpr long long int mod = 1000000007; using namespace std; string A,B; long long int dp1[100001][2][2][3][8],dp2[100001][2][2][3][8]; int main() { cin >> A>>B; int n = A.size(),p=B.size(); dp1[0][0][0][0][0] = 1; dp2[0][0][0][0][0] = 1; int tmp = n - 1; while(A[tmp]=='0'){ A[tmp] = '9'; tmp--; } A[tmp]--; if(A[0]=='0'){ A = A.substr(1); n--; } for (int i = 0; i < n; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { for (int l = 0; l < 3; l++) { for (int m = 0; m < 8; m++) { int x = j ? 9 : A[i] - '0'; for (int d = 0; d <= x; d++) { dp1[i + 1][j || d < x][k || d == 3][(l + d) % 3][(m * 10 + d) % 8] += dp1[i][j][k][l][m]; dp1[i + 1][j || d < x][k || d == 3][(l + d) % 3][(m * 10 + d) % 8] %= mod; } } } } } } for (int i = 0; i < p; i++){ for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { for (int l = 0; l < 3; l++) { for (int m = 0; m < 8; m++) { int x = j ? 9 : B[i] - '0'; for (int d = 0; d <= x; d++) { dp2[i + 1][j || d < x][k || d == 3][(l + d) % 3][(m * 10 + d) % 8] += dp2[i][j][k][l][m]; dp2[i + 1][j || d < x][k || d == 3][(l + d) % 3][(m * 10 + d) % 8] %= mod; } } } } } } long long int ans = 0; for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { for (int l = 0; l < 3; l++) { for (int m = 0; m < 8; m++) { if ((k || l == 0) && m != 0) { ans -= dp1[n][j][k][l][m]-dp2[p][j][k][l][m]; ans %= mod; } } } } } cout << (ans+mod)%mod << endl; }