結果
問題 |
No.260 世界のなんとか3
|
ユーザー |
![]() |
提出日時 | 2025-05-19 00:32:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 2,449 bytes |
コンパイル時間 | 2,223 ms |
コンパイル使用メモリ | 196,596 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-05-19 00:32:25 |
合計ジャッジ時間 | 4,228 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; static const ll MOD = 1000000007; // Decrement decimal string s by 1 string dec(const string &s) { int n = s.size(); if (n < 10) { // safe to convert ll v = stoll(s); return to_string(v - 1); } string t = s; int i = n - 1; // subtract 1 from last digit while (i >= 0) { if (t[i] > '0') { t[i]--; break; } else { t[i] = '9'; i--; } } // remove leading zero if any if (t[0] == '0') { t.erase(t.begin()); } return t; } // Compute result f(s) ll f(const string &s) { int nd = s.size(); vector<int> ds(nd); for (int i = 0; i < nd; ++i) ds[i] = s[i] - '0'; // dp[j][b3][m3][m8] static ll dp[2][2][3][8]; static ll ndp[2][2][3][8]; // init memset(dp, 0, sizeof(dp)); dp[0][0][0][0] = 1; for (int i = 0; i < nd; ++i) { memset(ndp, 0, sizeof(ndp)); for (int j = 0; j < 2; ++j) { for (int b3 = 0; b3 < 2; ++b3) { for (int m3 = 0; m3 < 3; ++m3) { for (int m8 = 0; m8 < 8; ++m8) { ll cur = dp[j][b3][m3][m8]; if (!cur) continue; int to = (j == 0 ? ds[i] : 9); for (int x = 0; x <= to; ++x) { int nj = j | (x < to); int nb3 = b3 | (x == 3); int nm3 = (10 * m3 + x) % 3; int nm8 = (10 * m8 + x) % 8; ndp[nj][nb3][nm3][nm8] = (ndp[nj][nb3][nm3][nm8] + cur) % MOD; } } } } } // swap dp and ndp memcpy(dp, ndp, sizeof(dp)); } ll res = 0; for (int j = 0; j < 2; ++j) { for (int b3 = 0; b3 < 2; ++b3) { for (int m3 = 0; m3 < 3; ++m3) { for (int m8 = 1; m8 < 8; ++m8) { if (b3 || m3 == 0) { res = (res + dp[j][b3][m3][m8]) % MOD; } } } } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); string A, B; if (!(cin >> A >> B)) return 0; ll ans = (f(B) - f(dec(A)) + MOD) % MOD; cout << ans; return 0; }