結果

問題 No.528 10^9と10^9+7と回文
ユーザー ei1333333
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0