【集训DAY N】number【数位DP】【状态压缩】

思路：

直接数位DP，然后状态要用变进制数压缩

$code$

#include
#include
#include

#define mod 998244353

using namespace std;

int m, len;
int val[100], a[10], f[60001][101];
char s[22];

inline int dfs(register int x, register int st, register int k) {
	if(x == 0) {
		if(k == 0) return 1;
		return 0;
	}
	if(f[st][k] != -1) return f[st][k];
	register int tmp = 0;
	for(register int i = (st ? 0 : 1); i <= 9; ++ i)
		if(st / val[i] % (a[i] + 1) < a[i])
			tmp = (tmp + dfs(x - 1, st + val[i], (k * 10 + i) % m)) % mod;
	return f[st][k] = tmp;
}

int main() {
	scanf("%s", s + 1);
	scanf("%d", &m); 
	memset(f, -1, sizeof(f));
	len = strlen(s + 1);
	val[0] = 1;
	for(int i = 1; i <= len; ++ i) a[s[i] - '0'] ++;
	for(int i = 1; i <= 10; ++ i)
		val[i] = val[i - 1] * (a[i - 1] + 1);
	printf("%d", dfs(len, 0, 0));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37