結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー eQeeQe
提出日時 2021-03-05 22:56:24
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,883 bytes
コンパイル時間 863 ms
コンパイル使用メモリ 88,968 KB
実行使用メモリ 58,956 KB
最終ジャッジ日時 2024-10-07 04:17:23
合計ジャッジ時間 5,744 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#include <bits/stdc++.h>>
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define pt(sth) cout << sth << "\n"
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
typedef long long ll;
typedef pair<ll, ll> pll;
template<class T>bool chmax(T &a, const T &b) {if(a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if(b<a) {a=b; return 1;} return 0;}
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;
//static const ll MOD=998244353;
//for(i=0;i<N;i++) cin>>a[i];

typedef vector<ll> v1D;
typedef vector<v1D> v2D;
typedef vector<v2D> v3D;


ll mop(ll x, ll n) {
  ll res=1;
  while(n>0) {
    if(n&1) (res*=x)%=MOD;
    (x*=x)%=MOD;
    n>>=1;
  }
  return res;
}

v3D dp(MAX/10,v2D(100,v1D(2,0)));


int main(void) {
  ll i, j, k;
  
  string s;cin>>s;
  ll N=s.size();
  
  dp[1][s[0]-'0'][1]=1;
  for(i=1;i<N;i++){
    for(j=0;j<100;j++){
      
      ll max=s[i]-'0';
      //0->0
      for(k=1;k<10;k++){
        (dp[i+1][(j*k)%100][0]+=dp[i][j][0])%=MOD;
      }
      
      //1->0
      for(k=1;k<max;k++){
        (dp[i+1][(j*k)%100][0]+=dp[i][j][1])%=MOD;
      }
      
      //1->1
      if(max)
        (dp[i+1][(j*max)%100][1]+=dp[i][j][1])%=MOD;
      
    }
  }
  
  
  ll ans=(dp[N][0][0]+dp[N][0][1])%MOD;
  for(i=2;i<=N-1;i++){
    ll s=mop(9, i);
    ll a50=mop(8, i);
    ll a51=i*mop(8,i-1)%MOD;
    ll a20=mop(5, i);
    ll a21=i*2%MOD*mop(5,i-1)%MOD;
    
    
    ll c=mop(4,i);
    ll d=i*mop(4,i-1)%MOD;
    ll d2=i*2%MOD*mop(4,i-1)%MOD;
    ll e=i*2%MOD*(i-1)%MOD*mop(4,i-2)%MOD;
    (ans+=(s-a50-a51-a20-a21+c+d+d2+e+MOD*4))%=MOD;
    
  }
  
  pt(ans);
  
  
  
  
  
}
0