Description：

给定正整数 $ n,m$ ，问有多少个正整数满足： $(1)$ 不含前导 $ 0$ ； $ (2)$ 是 $ m $ 的倍数； $ (3)$ 可以通过重排列各个数位得到 $ n$ 。

$1\le n \le10^{20}$ $1\le m \le 100$

Solution：

数位 $DP$ ，第三个条件表示 $k$ 中各个数字个数与 $n$ 相同， $f[i][j]$ 表示剩余 $n$ 中的数字个数状压起来为 $i$ ，对 $m$ 取模结果是 $j$ 的方案数，最大的问题是怎么状压 $i$ ，因为数字最大的出现个数可能是 $20$ ，如果用 $map$ 维护 $vector$ 最慢的点跑到 $12s$ ，于是可以以 $n$ 中每一位的个数 $+1$ 作为每一位的进制把状态压成一个数，就可以开数组了。

Code：

#pragma GCC optimize(3)

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int m;

int tot;

#define MOD 998244353

int cntbit[10];

inline int encode(int kcnt[])

{

	register int res = 0;

	for(register int i = 0;i <= 9;++i)

		res = res * (cntbit[i] + 1) + kcnt[i];

	return res;

}

int f[60000][101];

bool v[60000][101];

int dfs(int pos,bool zero,int k[],int mod)

{

	if(pos == 0)

	{

		if(mod == 0)return 1;

		else return 0;

	}

	register int code = encode(k);

	if(v[code][mod])return f[code][mod];

	register long long res = 0;

	for(register int i = 0;i <= 9;++i)

	{

		if(!zero && i == 0)continue;

		if(k[i] == 0)continue;

		--k[i];

		res += dfs(pos - 1,true,k,(mod * 10 + i) % m);

		++k[i];

	}

	res %= MOD;

	f[code][mod] = res;v[code][mod] = true;

	return res;

}

int stcnt[10];

int main()

{

	freopen("number.in","r",stdin);

	freopen("number.out","w",stdout);

	register char c = getchar();

	while(c < '0' || c > '9')c = getchar();

	register int k;

	while('0' <= c && c <= '9')

	{

		++tot;

		k = (c ^ 48);

		stcnt[k] += 1;

		cntbit[k] += 1;

		c = getchar();

	}

	scanf("%d",&m);

	printf("%d\n",dfs(tot,false,stcnt,0));

	fclose(stdin);

	fclose(stdout);

	return 0;

}