算法
(数位DP)
记 dp[i][S][j]
表示从高位开始确定的前 $i$ 位数的数字集合为 $S$ ,$j = \begin{cases} 0 : \text{和} N \text{匹配} \\\ 1 : \text{小于} N \end{cases}$
的个数
可类似地定义出关于数字总和的 ${\rm dp}$
最后的答案只需统计包含序列 $C$ 的集合 $S$ 的数字总和即可
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
using mint = modint998244353;
mint dp[10005][1<<10][2];
mint ds[10005][1<<10][2];
int main() {
string N;
cin >> N;
int n = N.size();
int cs = 0;
{
int m;
cin >> m;
rep(i, m) {
int c;
cin >> c;
cs |= 1<<c;
}
}
rep(i, n) {
int ni = i+1;
int d = N[i]-'0';
rep(s, 1<<10)rep(j, 2) {
mint num = dp[i][s][j];
mint sum = ds[i][s][j];
rep(x, 10) {
int ns = s, nj = j;
if (j == 0 and x > d) continue;
if (x < d) nj = 1;
ns |= 1<<x;
dp[ni][ns][nj] += num;
ds[ni][ns][nj] += sum*10 + num*x;
if (s == 0 and (i==0?0:1) == j and x != 0) {
dp[ni][ns][nj] += 1;
ds[ni][ns][nj] += x;
}
}
}
}
mint ans;
rep(s, 1<<10) if ((s&cs) == cs) rep(j, 2) {
ans += ds[n][s][j];
}
cout << ans.val() << '\n';
return 0;
}