結果

問題 No.528 10^9と10^9+7と回文
コンテスト
ユーザー tossy
提出日時 2017-06-10 00:25:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,595 bytes
コンパイル時間 1,507 ms
コンパイル使用メモリ 170,096 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-01 11:27:11
合計ジャッジ時間 2,959 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600
#define MOD 1000000007
#define DOM 1000000000

#define MX 100005

string s;
int n;
long mod;
long solve(){
  long ans = 0;
  {
    long tmp = 9;
    repl(i,1,n){
      (ans += tmp)%=mod;
      if(i%2==0) tmp = (tmp*10)%mod;
    }
    ans %= mod;
  }

  bool countjust = true;
  vector<long> tmp(n+1);
  tmp[0] = 1;
  repl(i,1,n){
    if(i%2==1) tmp[i]=tmp[i-1]*10%mod;
    else tmp[i] = tmp[i-1];
  }
  rep(i,(n+1)/2){
    rep(j,10) if(i!=0 || j>0){
      int x = s[i], y = s[n-i-1];
      if(j<x){
        if(n-2*(i+1)<=0) ans++;
        else (ans += tmp[n-2*(i+1)])%=mod;
      }
      if(x<=y && j==x) break;
      if(x>y && j==x){
        countjust = false;
        break;
      }
    }
    ans %=mod;
  }
  if(!countjust && n%2==0 && s[n/2-1]<s[n/2]) countjust=true;

  return (ans + countjust)%mod;
}


int main(){
  cin>>s;
  n =s.size();
  rep(i,n) s[i] -= '0';

  mod = DOM;
  cout << solve() << endl;
  mod = MOD;
  cout << solve() << endl;

  return 0;
}
0