結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー eQeeQe
提出日時 2021-03-05 23:13:33
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,885 bytes
コンパイル時間 998 ms
コンパイル使用メモリ 88,412 KB
実行使用メモリ 59,068 KB
最終ジャッジ日時 2024-04-16 11:11:20
合計ジャッジ時間 5,854 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
権限があれば一括ダウンロードができます

ソースコード

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-1;
  for(i=3;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