ABC194 F - Digits Paradise in Hexadecimal

問題

atcoder.jp

解法

いわゆる「桁DP」と呼ばれるやつ まあ桁DPがよく分からなくてもとりあえず動的計画法っぽいことを認識できれば良し（種類数を管理しながら・・・とかを考えるとDPでやりたいお気持ちになってくる）
dp=(上からi桁目まで見た時にn未満になることが分かるような条件を満たす数の個数）
として考える．
今まで出てきた数字を全部管理しちゃうとかすると，
dp[n.size()][1<<16][k]
とかみたいなテーブルがまず思いつくが，当然壊れちゃうのでもう少し工夫する必要がある．

まずnより小さくなる数sにどういう性質があるかを考えてみると，以下のような性質が見つかる．
・nの桁数より少ない
・nと桁数は一致していて，頭の方は同じだがn[i]<s[i]となるような箇所より前にn[i]>s[i]となるような箇所が存在する

前者の条件については簡単で，後ろの方の桁から始めればよい． 後者については，その小さくなるのが確定する桁iについて，0~n[i]-1までを考えてやればいい．ただし，その数字が今まで出てきたことがある場合とそうでない場合で種類数が変わってしまうため，その部分は今まで出てきた数字を管理して探索してやればいい．
今までの桁で小さくなるのが確定している数字については，どの数字を使ってもn未満になるが，今まで出てきた種類数をjとすれば，出てきていない種類数は16-jであり，どっちを使うかで種類数が変わるためその部分の遷移を記述すれば良い．
以上のことを考えると以下のようなdpテーブルができ，これは空間計算量O(k*n.size())となってなんとかなりそうなのが分かる
dp[i][j]:頭から見てi桁目まで見た時に，n未満となるのが確定していて，出てくる種類がちょうどj個となるような数字の個数
ただし問題文はn"以下"を求めるように言っているので，もしnそのものが条件を満たす場合はそれを答えに加える必要があることに注意する．

提出

atcoder.jp

#include<bits/stdc++.h>
#include <atcoder/modint>
using namespace atcoder;
using namespace std;
using mint=atcoder::modint1000000007;
signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  string n;cin>>n;
  int k;cin>>k;
  int sz=(int)n.size();

  std::vector<std::vector<mint>> dp(sz+1,std::vector<mint> (17,0));//dp[i][j]:上からi桁目まで見た時に数字がj種類出てきてかつnより小さくなるような数の個数.最終的に求める答えはdp[sz][k](+もしnそのものが条件を満たす場合は+1する)
  set<char>st;//今まで出てきた数字を管理する
  auto itoc=[&](int i)->char{//数字を文字に変更
    if(i<10)return (char)(i+'0');
    else return (char)(i-10+'A');
  };
  auto ctoi=[&](char c)->int{//文字を数字に変更
    if(isdigit(c))return c-'0';
    else return c-'A'+10;
  };

  for(int i=0;i<sz;i++){
    if(i)dp[i+1][1]+=15;//上から見た時にnより小さい桁から始まるとすると明らかに小さい

    //i-1桁目まで一致していて，i桁目で小さくなることが確定する場合を考える
    //n[i]より小さい数になれば明らかにその数はnより小さくなるが，その数字が今まで出てきたかどうかで種類数が変わるので，その部分は全探索
    int kind=(int)st.size();//これまでに出てきた数字の種類数
    for(int j=0;j<ctoi(n[i]);j++){
      if(kind==0 and j==0)continue;//先頭の桁が0になるのは上で数えるので飛ばす
      if(st.find(itoc(j))!=st.end()){//今まで出てきたやつ
        dp[i+1][kind]++;
      }else{//初めて出てくるやつ
        dp[i+1][kind+1]++;
      }
    }
    st.insert(n[i]);
    //今までで小さいのが確定している数字の遷移
    for(int j=0;j<=k;j++){
      dp[i+1][j]+=dp[i][j]*j;//今まで使った数字を使えばもちろん種類数は変わらない
      if(j+1<17)dp[i+1][j+1]+=dp[i][j]*(16-j);//今までに使ったことのない数字を使えば当然種類数は1だけ増える（配列外参照に注意）
    }
  }
  dp[sz][st.size()]++;//ｎぴったりの分の加算
  printf("%d\n",dp[sz][k]);
  return 0;
}