結果

問題 No.528 10^9と10^9+7と回文
ユーザー ei1333333
提出日時 2017-06-09 23:55:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,347 bytes
コンパイル時間 1,871 ms
コンパイル使用メモリ 161,672 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-22 20:23:15
合計ジャッジ時間 3,372 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define rep(i, n)for(int i=0;i<(n);i++)
using namespace std;

typedef long long int64;

int64 dp[100001][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 solve(string a, int MOD)
{
  memset(dp2, -1, sizeof(dp2));
  int64 ret = 0;
  for(int i = 0; i < a.size() - 1; i++) {
    ret += rec2(i - 1, MOD) * 9;
    ret %= MOD;
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  rep(i, a.size() / 2)
    rep(j, 2) {
      if(dp[i][j] == 0)continue;
      int g = (j ? 9 : a[i] - '0');
      rep(l, g + 1)(dp[i + 1][j || l < g] += dp[i][j]) %= MOD;
    }
  return (ret);
}

int main()
{
  string b;
  cin >> b;
  int MOD = 1e9;
  if(b.size() % 2 == 1) printf("%lld\n", (solve(b, MOD) + (dp[b.size() / 2][0] * (b[b.size() / 2] - '0') + dp[b.size() / 2][1] * 10)) % MOD);
  else printf("%lld\n", (solve(b, MOD) + dp[b.size() / 2][0] + dp[b.size() / 2][1] - 1 + MOD) % MOD);
  MOD = 1e9 + 7;
  if(b.size() % 2 == 1) printf("%lld\n", (solve(b, MOD) + (dp[b.size() / 2][0] * (b[b.size() / 2] - '0') + dp[b.size() / 2][1] * 10)) % MOD);
  else printf("%lld\n", (solve(b, MOD) + dp[b.size() / 2][0] + dp[b.size() / 2][1] - 1 + MOD) % MOD);

}
0