Variety of Digits
[Link](F - Variety of Digits (atcoder.jp))
题意
给你一个数字 n n n，和 m m m个一位数，问 1 1 1到 n n n中数位中含有这 m m m个数字的数的 s u m sum sum是多少。
思路
考虑数位 d p dp dp，从前往后枚举每一位，对每一位的合法填法进行分类讨论转移，进而不重不漏的划分集合，算贡献。
假设当前数为 a b c d e abcde abcde，我们枚举到了第三位，则将当前的集合划分为：
- 前缀属于 [ 1 , a b − 1 ] [1,ab-1] [1,ab−1]这样第三位可以填 [ 0 , 9 ] [0,9] [0,9]，因为前缀小于 a b ab ab所以第三位填什么都不会导致后面大于 a b c d e abcde abcde
- 前缀属于 0 0 0，这样第三位可以填 [ 1 , 9 ] [1,9] [1,9]，因为前缀为 0 0 0小于 a b ab ab，第三位可以随便填，但是 0 0 0没有意义所以只能填 [ 1 , 9 ] [1,9] [1,9]
- 前缀属于 a b ab ab即这个数，那么第三位可以填 [ 0 , c − 1 ] [0,c-1] [0,c−1]，因为要在范围内所以填 [ 0 , c − 1 ] [0,c-1] [0,c−1]都合法。为什么不填 c c c呢？因为我们填 c c c这个情况会被我们用前缀记录下来。（这样下次转移的时候我的状态才是可以随便选的）
这里用状态压缩来记录这 m m m个数，假设到了第 i i i位，我需要知道前 i − 1 i-1 i−1位的不同状态的和，转移的话枚举当前这一位填什么，因为多了一位所以前 i − 1 i-1 i−1位的和要 × 10 \times 10 ×10，发现我们不知道这一位填的这个数可以接到多少个不同的方案后面，因此还要维护一个前 i − 1 i-1 i−1位不同方案的数目。
状态表示为： f c [ i ] [ j ] : 填 了 前 i 位 且 状 态 为 j 的 方 案 数 ， f s [ i ] [ j ] : 填 了 前 i 位 且 状 态 为 j 的 所 有 方 案 的 总 和 fc[i][j]:填了前i位且状态为j的方案数，fs[i][j]:填了前i位且状态为j的所有方案的总和 fc[i][j]:填了前i位且状态为j的方案数，fs[i][j]:填了前i位且状态为j的所有方案的总和
状态转移：对于每一位按照集合划分转移即可。
最后要判断一下前缀(原数)是否合法。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <iomanip>
#include <deque>
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 998244353;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
LL fc[N][(1 << 10) + 1], fs[N][(1 << 10) + 1];
// fc[i][j]：前i个数字且状态为j的方案数
// fs[i][j]：前i个数字且状态为j的数的和
// 数位dp -> 分类讨论 对于每一位 保证算贡献的数都在范围内, 重点在于对状态的贡献
// xxxxaxxxx 分3类
//1. xxxxx非零且小于原数 则第i位 可以任意取 [0,9]
//2. xxxx为零 则第i位 可以取 [1,9]
//3. xxxx 为原数字 则第i位 可以取得[0, a - 1]
// 最后单独算一下原数是否符合即可
// 转移由前面转移过来
// 变成连续问题 直接连续来取
int main() {
ios::sync_with_stdio(false), cin.tie(0);
string str; cin >> str;
int n = str.size();
for (int i = 0; i < n; i ++) a[i] = str[i] - '0';
cin >> m;
int mask = 0;
for (int i = 0; i < m; i ++) {
int x; cin >> x;
mask |= 1 << x;
}
int last = a[0], prebit = 1 << a[0];
// 相当于前缀前缀且全为0的情况 因此只能由[1, a[i]) 转移过来
for (int i = 1; i < a[0]; i ++) {
(fc[0][1 << i] += 1) % mod;
(fs[0][1 << i] += i) % mod;
}
for (int i = 1; i < n; i ++) {
// 保证转移的时候这一位可以随便选取
for (int j = 1; j < (1 << 10); j ++)
for (int x = 0; x < 10; x ++) {
fc[i][j | (1 << x)] = (fc[i][j | (1 << x)] + fc[i - 1][j] + mod) % mod;
fs[i][j | (1 << x)] = (fs[i][j | (1 << x)] + fs[i - 1][j] * 10 + fc[i - 1][j] * x + mod) % mod;
}
for (int x = 1; x < 10; x ++) {
fc[i][1 << x] = (fc[i][1 << x] + 1 + mod) % mod;
fs[i][1 << x] = (fs[i][1 << x] + x + mod) % mod;
}
// 不填满 前缀相同 如果这一位填到a[i] 那么f[i - 1][j]的这些已有的状态里就存在了abcd 就无法直接转移了，相当于一个分类讨论
for (int x = 0; x < a[i]; x ++) {
fc[i][prebit | (1 << x)] = (fc[i][prebit | (1 << x)] + 1 + mod) % mod;
fs[i][prebit | (1 << x)] = (fs[i][prebit | (1 << x)] + (LL)last * 10 + x + mod) % mod;
}
last = ((LL)last * 10 + a[i] + mod) % mod;
prebit = prebit | (1 << a[i]);
}
// cout << last << endl;
LL res = 0;
for (int j = 0; j < (1 << 10); j ++)
if ((j & mask) == mask) res = (res + fs[n - 1][j]) % mod;
if ((prebit & mask) == mask) res = (res + last) % mod;
cout << res << endl;
return 0;
}