結果

問題 No.315 世界のなんとか3.5
ユーザー mkawa2
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 confirmed
for (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 exactly
for (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 digit
if (i) {
for (int d = 1; d < 10; ++d) {
ndp[d == 3][d] += 1;
}
}
// Update exactly
jf |= (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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0