結果

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

ソースコード

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,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*mop(5,i-1)%MOD;
    
    
    ll c=mop(4,i);
    ll d=i*mop(4,i-1)%MOD;
    ll d2=i*2*mop(4,i-1)%MOD;
    ll e=i*2*(i-1)%MOD*mop(4,i-2)%MOD;
    (ans+=(s-a50-a51-a20-a21+c+d+d2+e+MOD*4))%=MOD;
    
  }
  
  pt(ans);
  
  
  
  
  
}
0