結果
問題 | No.315 世界のなんとか3.5 |
ユーザー |
![]() |
提出日時 | 2024-09-24 00:17:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 748 ms / 2,000 ms |
コード長 | 2,649 bytes |
コンパイル時間 | 7,097 ms |
コンパイル使用メモリ | 100,924 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 06:06:04 |
合計ジャッジ時間 | 12,944 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <iostream>#include <vector>using namespace std;const int md = 1e9 + 7;long long digitdp(vector<int>& aa, bool eq, int p) {int k = to_string(p).length();p = stoi(to_string(p));long long res = 0;vector<vector<long long>> dp(2, vector<long long>(24, 0));int jf = 0, jm = 0;for (size_t i = 0; i < aa.size(); ++i) {vector<vector<long long>> ndp(2, vector<long long>(24, 0));// Transition from less than confirmedfor (int f = 0; f < 2; ++f) {for (int m = 0; m < 24; ++m) {long long pre = dp[f][m] % md;if (pre == 0) continue;for (int d = 0; d < 10; ++d) {int nf = f | (d == 3);int nm = (m * 10 + d) % 24;ndp[nf][nm] += pre;}}}// Transition from exactlyfor (int d = (i == 0); d < aa[i]; ++d) {int nf = jf | (d == 3);int nm = (jm * 10 + d) % 24;ndp[nf][nm] += 1;}// Start from this digitif (i) {for (int d = 1; d < 10; ++d) {ndp[d == 3][d] += 1;}}// Update exactlyjf |= (aa[i] == 3);jm = (jm * 10 + aa[i]) % 24;dp = ndp;if (i == aa.size() - k) {int s=0;for (int j=i+1;j<aa.size();j++) s+=aa[j];if ((jf || jm % 3 == 0) && jm % 8 == 0 && s) res -= 1;for (int f = 0; f < 2; ++f) {for (int m = 0; m < 24; ++m) {if ((f || m % 3 == 0) && m % 8 == 0) {res -= dp[f][m];res %= md;}}}}}if (eq) {long long pos = 0;int l = max(0, (int)aa.size() - 5);for (size_t i = l; i < aa.size(); ++i) {pos = (pos * 10 + aa[i]) % p;}if ((jf || jm % 3 == 0) && pos) res += 1;}for (int f = 0; f < 2; ++f) {for (int m = 0; m < 24; ++m) {if (f || m % 3 == 0) {res += dp[f][m];res %= md;}}}return res;}int main() {string a, b, p;cin >> a >> b >> p;vector<int> aa(a.size()), bb(b.size());for (size_t i = 0; i < a.size(); ++i) aa[i] = a[i] - '0';for (size_t i = 0; i < b.size(); ++i) bb[i] = b[i] - '0';int k = p.size();long long ans = digitdp(bb, true, stoi(p)) - digitdp(aa, false, stoi(p));cout << (ans % md + md) % md << endl;return 0;}