結果

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

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

string S;
int64 dp[1000001][2];
int64 dp2[1000001];

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, const int mod)
{
  if(~dp[idx][free]) return (dp[idx][free]);
  if(S.size() / 2 == idx) {
    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) continue;
    (ret += rec(idx + 1, free | (i != end), mod)) %= mod;
  }
  return (dp[idx][free] = 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, 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;
}
0