結果
問題 | No.260 世界のなんとか3 |
ユーザー | yuppe19 😺 |
提出日時 | 2018-11-02 12:07:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 348 ms / 2,000 ms |
コード長 | 2,053 bytes |
コンパイル時間 | 1,360 ms |
コンパイル使用メモリ | 98,892 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-20 12:59:02 |
合計ジャッジ時間 | 6,832 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 348 ms
6,820 KB |
testcase_04 | AC | 340 ms
6,820 KB |
testcase_05 | AC | 71 ms
6,816 KB |
testcase_06 | AC | 43 ms
6,816 KB |
testcase_07 | AC | 230 ms
6,820 KB |
testcase_08 | AC | 165 ms
6,820 KB |
testcase_09 | AC | 91 ms
6,820 KB |
testcase_10 | AC | 262 ms
6,816 KB |
testcase_11 | AC | 249 ms
6,816 KB |
testcase_12 | AC | 145 ms
6,820 KB |
testcase_13 | AC | 43 ms
6,816 KB |
testcase_14 | AC | 219 ms
6,820 KB |
testcase_15 | AC | 59 ms
6,820 KB |
testcase_16 | AC | 196 ms
6,820 KB |
testcase_17 | AC | 155 ms
6,816 KB |
testcase_18 | AC | 148 ms
6,820 KB |
testcase_19 | AC | 196 ms
6,816 KB |
testcase_20 | AC | 135 ms
6,816 KB |
testcase_21 | AC | 120 ms
6,816 KB |
testcase_22 | AC | 224 ms
6,816 KB |
testcase_23 | AC | 22 ms
6,816 KB |
testcase_24 | AC | 169 ms
6,820 KB |
testcase_25 | AC | 177 ms
6,820 KB |
testcase_26 | AC | 100 ms
6,820 KB |
testcase_27 | AC | 2 ms
6,816 KB |
testcase_28 | AC | 202 ms
6,816 KB |
testcase_29 | AC | 212 ms
6,816 KB |
ソースコード
#include <cmath> #include <iostream> #include <vector> using namespace std; using i64 = int64_t; constexpr int mod = static_cast<int>(powl(10, 9)) + 7; vector<int> p10; // p10[i] := 10**i % 24 i64 f(string s) { int n = static_cast<int>(s.size()); // dp[フラグ][3がつくか?][3での余り][8での余り] := 個数 vector<vector<vector<vector<i64>>>> dp(3, vector<vector<vector<i64>>>(2, vector<vector<i64>>(3, vector<i64>(8, 0)))); dp[1][0][0][0] = 1; for(int i=n-1; i>=0; --i) { vector<vector<vector<vector<i64>>>> ndp(3, vector<vector<vector<i64>>>(2, vector<vector<i64>>(3, vector<i64>(8, 0)))); for(int flag=0; flag<3; ++flag) { for(int has3=0; has3<2; ++has3) { for(int rem=0; rem<24; ++rem) { if(!dp[flag][has3][rem%3][rem%8]) { continue; } for(int d=0; d<10; ++d) { int dflag = d == (s[i] - '0'); if(d > s[i] - '0') { dflag = 2; } int nflag = flag * dflag; if(nflag >= 2) { nflag = 2; } if(flag == 0 && dflag == 2) { nflag = 2; } int nrem = (rem + p10[n-1-i] * d) % 24; int nhas3 = has3 || (d == 3); ndp[nflag][nhas3][nrem%3][nrem%8] += dp[flag][has3][rem%3][rem%8]; ndp[nflag][nhas3][nrem%3][nrem%8] %= mod; } } } } dp = ndp; } i64 res = 0; for(int flag=0; flag<2; ++flag) { for(int rem8=1; rem8<8; ++rem8) { for(int rem3=0; rem3<3; ++rem3) { res += dp[flag][1][rem3][rem8]; res %= mod; } res += dp[flag][0][0][rem8]; res %= mod; } } return res; } void minus1(string &s) { int n = s.size(); for(int i=n-1; i>=0; --i) { if(s[i] == '0') { s[i] = '9'; } else { s[i] -= 1; break; } } } int main(void) { p10.resize(10010); p10[0] = 1; for(int i=0; i<10005; ++i) { p10[i+1] = p10[i] * 10 % 24; } string a, b; cin >> a >> b; minus1(a); i64 r0 = f(a), r1 = f(b); i64 res = f(b) - f(a); res += mod; res %= mod; printf("%ld\n", res); return 0; }