ARC52 D-9

D - 9

がより小さい時

桁DPをすればいい
:下桁自由に使えて[値-各桁の和 mod K]がの時の通り
状態数が、遷移がなので計算量は

がより大きい時

をからまで愚直に回してcheckすればいい
各桁の和 は未満なので、 がになったらにを足していい
回ごとに回各桁の和を計算をするので（各桁の和を計算するのに10回として）計算量は

#include <bits/stdc++.h>
using namespace std;

#define int long long
int MOD,ans,dp[15][123456];
int pw(int n,int k){
  assert(k>=0);
  int res=1;
  while(k){
    if(k&1)(res*=n)%=MOD;
    (n*=n)%=MOD;
    k>>=1;
  }
  return res;
}

int f(int a,int b){//下a桁自由に使えて、ノーマル側がb先行している時の通り
  if(~dp[a][b])return dp[a][b];
  if(!a)return !b;
  int res=0;
  for(int i=0;i<10;i++)res+=f(a-1,(b+i*pw(10,a-1)+MOD-i)%MOD);
  return dp[a][b]=res;
}

bool g(int a){//愚直
  int res=0,b=a%MOD;
  while(a){
    res+=a%10;
    a/=10;
  }
  return (res%MOD)==b;
}

signed main(){
  memset(dp,-1,sizeof(dp));
  cin>>MOD;

  if(MOD>100000){
    int M;cin>>M;
    for(int i=1;i<=M;i++){
      ans+=g(i);
      if(i%MOD==100)i+=MOD-99;
    }
  }
  else{
    string m;cin>>m;
    int S=m.size(),now=0;
    for(int i=0;i<S;i++){
      int T=pw(10,S-i-1)+MOD-1;
      for(int j=0;j<m[i]-'0';j++){
        ans+=f(S-1-i,now);
        (now+=T)%=MOD;
      }
    }
    ans+=!now;//Mが条件を満たす時
    ans--;//0を除く
  }
  cout<<ans<<endl;
}

Submission #11936944 - AtCoder Regular Contest 052