結果
問題 | No.528 10^9と10^9+7と回文 |
ユーザー |
![]() |
提出日時 | 2017-06-10 00:15:16 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 64 ms / 1,000 ms |
コード長 | 1,552 bytes |
コンパイル時間 | 1,323 ms |
コンパイル使用メモリ | 159,848 KB |
実行使用メモリ | 13,096 KB |
最終ジャッジ日時 | 2024-07-23 18:30:19 |
合計ジャッジ時間 | 2,642 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long int64;string S;int64 dp[100001][2][2];int64 dp2[100001];int64 rec2(int idx, const int mod){if(idx <= 0) return (1);if(idx % 2 == 1) return (rec2(idx - 1, mod) * 10 % mod);if(~dp2[idx]) return (dp2[idx]);return (dp2[idx] = rec2(idx - 2, mod) * 10 % mod);}int64 rec(int idx, bool free, bool less, const int mod){if(~dp[idx][free][less]) return (dp[idx][free][less]);if(S.size() / 2 == idx) {if(less && !free) {if(S.size() % 2 == 0) return (0);if(S[idx] == '0') return (0);return (S[idx] - '0');}if(S.size() % 2 == 1) return (free ? 10 : S[idx] - '0' + 1);else return (1);}int64 ret = 0;int end = free ? 9 : S[idx] - '0';for(int i = 0; i <= end; i++) {if(idx == 0 && i == 0) continue;bool nt = free | (i != end);if(!nt && S[S.size() - idx - 1] - '0' < i) {(ret += rec(idx + 1, free | (i != end), true, mod)) %= mod;} else {(ret += rec(idx + 1, free | (i != end), less & (S[S.size() - idx - 1] - '0' <= i), mod)) %= mod;}}return (dp[idx][free][less] = ret);}int64 ct(int mod){memset(dp, -1, sizeof(dp));memset(dp2, -1, sizeof(dp2));int64 ret = 0;for(int i = 0; i < S.size() - 1; i++) {ret += rec2(i - 1, mod) * 9;ret %= mod;}return ((ret + rec(0, 0, 0, mod)) % mod);}int main(){cin >> S;if(S.size() == 1) {cout << S << endl << S << endl;return (0);}cout << ct(1e9) << endl;cout << ct(1e9 + 7) << endl;}