結果
問題 | No.528 10^9と10^9+7と回文 |
ユーザー |
![]() |
提出日時 | 2019-09-04 13:34:58 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 20 ms / 1,000 ms |
コード長 | 1,191 bytes |
コンパイル時間 | 864 ms |
コンパイル使用メモリ | 101,916 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-23 18:35:47 |
合計ジャッジ時間 | 1,827 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;ll MOD;ll solve(string s){int n=s.size();if(n==1) return s[0]-'0';ll dp[2][100010]={};dp[0][0]=1, dp[1][0]=s[0]-'0'-1;for(int i=1; i<n; i++){(dp[1][i]+=dp[1][i-1]*10)%=MOD;(dp[0][i]+=dp[0][i-1])%=MOD;(dp[1][i]+=dp[0][i-1]*(s[i]-'0'))%=MOD;}ll ans=dp[1][(n-1)/2];bool nuo=1;for(int i=(n-1)/2+1; i<n; i++){if(s[i]>s[n-1-i]) break;else if(s[i]<s[n-1-i]){nuo=0; break;}}if(nuo) ans=(ans+1)%MOD;ll p[100010];p[0]=1;for(int i=1; i<=n; i++) p[i]=p[i-1]*10%MOD;for(int i=1; i<n; i++){(ans+=(p[(i+1)/2]-p[(i-1)/2]+MOD))%=MOD;}return ans;}int main(){string s; cin>>s;MOD=1e9;cout<<solve(s)<<endl;MOD=1e9+7;cout<<solve(s)<<endl;return 0;}