結果
問題 | No.528 10^9と10^9+7と回文 |
ユーザー |
![]() |
提出日時 | 2017-06-10 00:40:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 1,000 ms |
コード長 | 1,577 bytes |
コンパイル時間 | 801 ms |
コンパイル使用メモリ | 83,952 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 18:31:05 |
合計ジャッジ時間 | 1,994 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <iomanip> #include <cassert> using namespace std; #define GET_ARG(a,b,c,F,...) F #define REP3(i,s,e) for (i = s; i <= e; i++) #define REP2(i,n) REP3 (i,0,(int)(n)-1) #define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__) #define RREP3(i,s,e) for (i = s; i >= e; i--) #define RREP2(i,n) RREP3 (i,(int)(n)-1,0) #define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__) #define DEBUG(x) cerr << #x ": " << x << endl int dp[2][50001][2]; int main(void) { string s; cin >> s; int i, j, k, l, n = s.size(); int mod[2]; mod[0] = 1e9; mod[1] = 1e9+7; dp[0][0][1] = 1; dp[1][0][1] = 1; REP (i,2) REP (j,(n+1)/2) REP (k,10) { if (j == 0 && k == 0) continue; dp[i][j+1][0] = (dp[i][j+1][0] + dp[i][j][0]) % mod[i]; if (k < s[j] - '0') dp[i][j+1][0] = (dp[i][j+1][0] + dp[i][j][1]) % mod[i]; if (k == s[j] - '0') dp[i][j+1][1] = (dp[i][j+1][1] + dp[i][j][1]) % mod[i]; } int ans[2] {}; long long x[2] {9,9}; REP (i,2) REP (j,n/2) { ans[i] = (ans[i] + x[i]) % mod[i]; if ((j+1) * 2 <= n-1) ans[i] = (ans[i] + x[i]) % mod[i]; x[i] = (x[i] * 10) % mod[i]; } REP (i,2) ans[i] = (ans[i] + dp[i][(n+1)/2][0]) % mod[i]; bool ok = true; RREP (i,n/2) { if (s[i] < s[n-1-i]) break; ok &= s[i] == s[n-1-i]; } REP (i,2) ans[i] = (ans[i] + ok) % mod[i]; REP (i,2) cout << ans[i] << endl; return 0; }