結果

問題 No.528 10^9と10^9+7と回文
ユーザー ei1333333ei1333333
提出日時 2017-06-10 00:14:14
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,990 bytes
コンパイル時間 2,800 ms
コンパイル使用メモリ 162,592 KB
実行使用メモリ 13,164 KB
最終ジャッジ日時 2023-10-24 03:52:22
合計ジャッジ時間 4,511 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 4 ms
7,568 KB
testcase_03 AC 4 ms
7,568 KB
testcase_04 AC 4 ms
7,568 KB
testcase_05 AC 3 ms
7,568 KB
testcase_06 AC 4 ms
7,568 KB
testcase_07 AC 4 ms
7,568 KB
testcase_08 AC 4 ms
7,568 KB
testcase_09 AC 4 ms
7,568 KB
testcase_10 AC 65 ms
13,164 KB
testcase_11 AC 65 ms
13,164 KB
testcase_12 AC 65 ms
13,164 KB
testcase_13 AC 65 ms
13,164 KB
testcase_14 AC 40 ms
10,912 KB
testcase_15 AC 37 ms
10,548 KB
testcase_16 AC 34 ms
10,300 KB
testcase_17 AC 28 ms
9,856 KB
testcase_18 AC 63 ms
12,888 KB
testcase_19 AC 21 ms
9,100 KB
testcase_20 AC 47 ms
11,484 KB
testcase_21 AC 28 ms
9,840 KB
testcase_22 AC 4 ms
7,568 KB
testcase_23 AC 4 ms
7,568 KB
testcase_24 AC 4 ms
7,620 KB
testcase_25 AC 10 ms
8,140 KB
testcase_26 AC 66 ms
13,164 KB
testcase_27 AC 18 ms
13,164 KB
権限があれば一括ダウンロードができます

ソースコード

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 dssp[100001];

void stuped(int K)
{
  for(int i = 1; i <= K; i++) {
    string s = to_string(i);
    string t = s;
    reverse(begin(t), end(t));
    dssp[i] += dssp[i - 1];
    dssp[i] += t == s;
  }
}

int main()
{
  cin >> S;
  cout << ct(1e9) << endl;
  cout << ct(1e9+7) << endl;
  /*
  stuped(100000);
  for(int i = 1; i <= 100000; i++) {
    S = to_string(i);
    if(S.size() == 1) continue;
    if(S.size() == 1) {
      cout << S << endl << S << endl;
      return (0);
    }

    if(dssp[i] != ct(1e9)) {
      cout << i << endl;
      return(0);
    }
  }

  cout << "OK" << endl;
*/
}
0