[ABC235] F - Variety of Digits

[Q] https://atcoder.jp/contests/abc235/tasks/abc235_f

桁DP[index][2^10][Nにピッタリかどうか] = それまでの総和
で管理。貰うDPで実装します。

Q. 何を言っているの？
A. 桁DPのテンプレート問題に沿った話をしてます。
[Q2] https://atcoder.jp/contests/dp/tasks/dp_s
これ、5回解いたことがあるんだ。
https://atcoder.jp/contests/dp/submissions?f.Task=dp_s&f.LanguageName=&f.Status=&f.User=merhorn
それでも解けないんだ…。悔しい悔しい…。構築までは、できたんだけど。

桁DPは、[Nにピッタリかどうか] の4要素の遷移を、慎重に構築。
1. false->falseの遷移を考える。
2. true->falseの遷移を考える。
3. true->trueの遷移を考える。
4. その桁から足し始める遷移を考える。

Q. 初期状態どうしよう？
A. 4,その桁から足し始める遷移 に含めればいい。1-3は、最初は何もしないもの。

Q. 答えは？
A. DP[N][回答bit][false/true] の総和。

DP遷移を確認

N=204 M=2
0 1
の場合。

・index 0
DP[1][0000000010][0]:100 // 100 ... 1だけを使って、index0までで作れる値の総和。100 のみ。
DP[1][0000000100][1]:200 // 200
//    ~~~~~~~~~~
//    9876543210 が使われているかどうか。

・index 1
DP[2][0000000010][0]:120 // 110 + 10 ... 1だけを使って、index1までで作れる値の総和
DP[2][0000000011][0]:100 // 100 ... 1と0を必ず使って、index1までで作れる値の総和
DP[2][0000000100][0]:20 // 20
DP[2][0000000101][1]:200 // 200
DP[2][0000000110][0]:120 // 120
DP[2][0000001000][0]:30
DP[2][0000001010][0]:130
DP[2][0000010000][0]:40
DP[2][0000010010][0]:140
DP[2][0000100000][0]:50
DP[2][0000100010][0]:150
DP[2][0001000000][0]:60
DP[2][0001000010][0]:160
DP[2][0010000000][0]:70
DP[2][0010000010][0]:170
DP[2][0100000000][0]:80
DP[2][0100000010][0]:180
DP[2][1000000000][0]:90
DP[2][1000000010][0]:190

・index 2
DP[3][0000000010][0]:123 // 111 + 11 + 1
                     ~~~ 123 になる必要があることに気づく!!

Q.
DP[3][0000000010][0]:123 = 111 + 11 + 1
わかっているのは、
DP[2][0000000010][0]:120 // 110 + 10
ここから、どうやって+2をしよう？
だって、2要素もっていることがわからない。

A. cnts[10000][2^10][2] として、DPの他に要素数もデータをとる。

Q. DP[3][0000000010][0] = 123

次の2通り
1.) index 1のfalseから受けつぐ
DP[2][0000000010][0] = 120 // 110 + 10
の2通りについて、
111 + 11 と +2 をする必要がある。
DP[2][][0]が、2通りの値をもっていることをおさえる必要が出てきた

DP[3][][0] += DP[2][][0] + cnts[2][][0] * 1;
                           ~~~~~~~~~~~~ 要素数だけ、増加量を増やす必要がある。

2.) index 2から新しく1を加算する
DP[3][][0] += 1;

あわせて
DP[3][][0] += 111 + 11  +  1;
              ~~~~~~~~(1)  ~(2)

Q.cnts[]の遷移
A.
1. その桁から、足し始める場合は、cnts[i+1] += 1。
2. 何かしら値を受け継ぐ場合は、cnts[i+1] += cnts[i]。

途切れてしまったけど、のこりの遷移確認
・index 2
DP[3][0000000010][0]:123 // 111 + 11 + 1
DP[3][0000000011][0]:321
DP[3][0000000100][0]:24
DP[3][0000000101][0]:422
DP[3][0000000110][0]:388
DP[3][0000000111][0]:423
DP[3][0000001000][0]:36
DP[3][0000001001][0]:30
DP[3][0000001010][0]:421
DP[3][0000001011][0]:233
DP[3][0000001100][0]:55
DP[3][0000001101][0]:203
DP[3][0000001110][0]:255
DP[3][0000010000][0]:48
DP[3][0000010001][0]:40
DP[3][0000010010][0]:454
DP[3][0000010011][0]:244
DP[3][0000010100][0]:66
DP[3][0000010101][1]:204
DP[3][0000010110][0]:266
DP[3][0000011000][0]:77
DP[3][0000011010][0]:277
DP[3][0000100000][0]:60
DP[3][0000100001][0]:50
DP[3][0000100010][0]:487
DP[3][0000100011][0]:255
DP[3][0000100100][0]:77
DP[3][0000100110][0]:277
DP[3][0000101000][0]:88
DP[3][0000101010][0]:288
DP[3][0000110000][0]:99
DP[3][0000110010][0]:299
DP[3][0001000000][0]:72
DP[3][0001000001][0]:60
DP[3][0001000010][0]:520
DP[3][0001000011][0]:266
DP[3][0001000100][0]:88
DP[3][0001000110][0]:288
DP[3][0001001000][0]:99
DP[3][0001001010][0]:299


・答えは
x は01自由として、
DP[3][xxxxxxxx11][0] と
DP[3][xxxxxxxx11][1] の総和をとればいい。
ans = 2606

実装

string S;
ll N, M;
vector<ll> C;
mint DP[10010][1 << 10][2];
mint cnts[10010][1 << 10][2];
mint mods[10010]; // 10^n%mod

int main() {
 cincout();

 cin >> S >> M;
 N = S.size();

 // mod10入れ
 mods[0] = 1;
 rep(i, N) { mods[i + 1] = mods[i] * 10; }

 rep(i, M) {
   ll c;
   cin >> c;
   C.push_back(c);
 }

 // DP
 rep(i, N) {
   ll a = S[i] - '0';
   // false->false
   rep(j, 1 << 10) {
     rep(k, 10) {
       if (DP[i][j][false] == 0) continue;
       DP[i + 1][j | (1 << k)][false] += DP[i][j][false];
       cnts[i + 1][j | (1 << k)][false] += cnts[i][j][false];
       if (k > 0) {
         DP[i + 1][j | (1 << k)][false] +=
             mods[N - i - 1] * k * cnts[i][j][false];
       }
     }
   }
   // true->false
   rep(j, 1 << 10) {
     if (DP[i][j][true] == 0) continue;
     rep(k, a) {
       DP[i + 1][j | (1 << k)][false] += DP[i][j][true];
       cnts[i + 1][j | (1 << k)][false] += cnts[i][j][true];
       if (k > 0) {
         DP[i + 1][j | (1 << k)][false] +=
             mods[N - i - 1] * k * cnts[i][j][true];
       }
     }
     // true->true
     DP[i + 1][j | (1 << a)][true] += DP[i][j][true] + mods[N - i - 1] * a;
     cnts[i + 1][j | (1 << a)][true] += cnts[i][j][true];
   }
   // その桁から、足し始めるやつ
   if (i == 0) {
     for (ll j = 1; j < a; ++j) {
       DP[i + 1][1 << j][false] += mods[N - i - 1] * j;
       cnts[i + 1][1 << j][false] += 1;
     }
     DP[i + 1][1 << a][true] += mods[N - i - 1] * a;
     cnts[i + 1][1 << a][true] += 1;
   } else {
     for (ll j = 1; j <= 9; ++j) {
       DP[i + 1][1 << j][false] += mods[N - i - 1] * j;
       cnts[i + 1][1 << j][false] += 1;
     }
   }
 }

 // 必須のbit
 ll bit = 0;
 rep(i, M) { bit |= (1 << C[i]); }
 
 // ans
 mint ans = 0;
 rep(i, 1 << 10) {
   if (__builtin_popcount(i & bit) != M) continue;
   ans += DP[N][i][false];
   ans += DP[N][i][true];
 }

 cout << ans << endl;
}

https://atcoder.jp/contests/abc235/submissions/28570370