题目链接：CF401D

题意：求将n的所有数位重新排列的所有数中，能够被m整除的数的个数


当数位DP专题做的，所以会想到记忆化来保存状态搞

n的所有数位重新排列怎么搞？记录有多少个数字就好，每个数字都得记录，就都得用一个新变量来保存

由于不能有前导0，所以构造出来会是这样：

dp【pos】【a0】【a1】【a2】【a3】【a4】【a5】【a6】【a7】【a8】【a9】

代表当前的前pos位，0出现a0次……9出现a9次

然后在dfs记忆化的时候，再来两个变量zero和flag，一个判断是否都是前导0，一个判断当前最高位能填多少

考虑下空间复杂度，肯定不行


那么就得换方法，既然是DP，不能用数位

有10^18次方在，状态压缩应该是必须有的吧

设计状态dp【s】【k】：当前状态为s，对m取余数为k的个数


只需要依次枚举n的每个数位上的值就好，相当于一个知道dfs深度（n的数位长度）的深搜，然后为了省时间记忆化一发


注意细节：

枚举第一位的时候，不能是0，避免前导0

在枚举的时候，每一位用过了要用flag数组标记，确保只用一次


#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define MOD 1000000007

LL dp[(1<<18)+20][105],n;
int m,len,digit[25];

LL dfs(int s,int k){
	if (s==(1<<len)-1) return k==0;
	if (dp[s][k]!=-1) return dp[s][k];
	LL ans=0;
	bool flag[10];
	memset(flag,false,sizeof(flag));
	for(int i=0;i<len;i++)
		if ((s&(1<<i))==0&&flag[digit[i]]==false){
			flag[digit[i]]=true;
			ans+=dfs(s|(1<<i),(k*10+digit[i])%m);
		}
	return dp[s][k]=ans;
}

LL solve(LL n){
	len=0;
	while(n){
		digit[len++]=n%10;
		n/=10;
	}
	LL ans=0;
	bool flag[10];
	memset(flag,false,sizeof(flag));
	for(int i=0;i<len;i++)
		if (digit[i]&&flag[digit[i]]==false){
			flag[digit[i]]=true;
			ans+=dfs(1<<i,digit[i]%m);
		}
	return ans;
}

int main()  
{
	//input;
    while(~scanf("%I64d%d",&n,&m))
    {
        memset(dp,-1,sizeof(dp));
        printf("%I64d\n",solve(n));
    }
    return 0;  
}