解题思路

首先我们发现这道题s的长度很小，所以考虑点暴力的做法，状压dp或搜索。本蒟蒻搜索永远调不对，所以就写了个状压dp。因为所有s里的数都要出现一次，并且最后的答案是要求整除，那么我们设$dp[S][k]$表示现在所选的状态集合为S，当前所选的数组成的数字对d取余后的值为k，这样就可以转移了。首先枚举所有的状态S，然后再枚举所有没有被选的数j，再枚举余数k即可转移。
　　转移方程为：$dp[S|(1<<(j-1))][(k*10+a[j])\%d]+=dp[S][k]$;但是这样写是错误的，因为没有考虑重复的排列，比如说s为"001"，结果发现“010”这个状态会被算两次。。看到有大佬直接用数学方法去重orz，本蒟蒻不太会，就记了个临时数组$b[i]$，表示当前要填的数字i有没有被填过，这样就可以避免一个位置放相同元素的情况了，具体看代码。时间复杂度为$O(T*len*d*2^{len})$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
const int MAXN = 11;

int T,d,a[MAXN],cnt,dp[1<<MAXN][1002];
bool b[MAXN];
char s[MAXN];

int main(){
	scanf("%d",&T);int len;
	while(T--){
		memset(dp,0,sizeof(dp));
		scanf("%s%d",s+1,&d);
		len=strlen(s+1);cnt=0;
		for(register int i=1;i<=len;i++) a[i]=s[i]-'0';//把所有数字存一下
		dp[0][0]=1;  //赋初值
		for(register int S=0;S<(1<<len)-1;S++){ //S表示当前所选的状态集合
			memset(b,0,sizeof(b));  //注意清零
			for(register int j=1;j<=len;j++)if(!(S&(1<<(j-1))) && !b[a[j]]){ //如果a[j]已经转移过就不能继续转移了,j表示遍历s中的各位数字。
				b[a[j]]=1;
				for(register int k=0;k<d;k++) //k表示对d取余后的数
					dp[S|(1<<(j-1))][(k*10+a[j])%d]+=dp[S][k];
			}
		}
		printf("%d\n",dp[(1<<len)-1][0]);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char ch[20];
ll d, len;
ll ans;
bool v[20];
ll inv[20], cnt[20];
int dp[1<<12][1100];
//dp[a][k]表示当选取的数的集合为a，这个数对d取模的结果是k时，符合这个条件的数的个数 
//易得在末尾加入的数会使这个数的余数增加k*10+ch[j]-'0'，再取模，就得到当前这个数对d取模的余数
//综上得状态转移方程dp[i|(1<<(j-1)][(k*10+ch[j]-'0')%d]+=dp[i][k]
//对于123434这种数字串内有重复数字的数字串，会发现，每个数字重复的个数会使结果增加重复个数的阶乘
//如123434，当第一个4排列完，第二个4能和它交换位置，而方程中记录的集合是数的位置是否被选而不是哪个数子备选，所以会增加一遍这个数字串的全排列 
void work(){
	memset(dp, 0, sizeof(dp));
	dp[0][0]=1;
	for(int i=0;i<(1<<len);i++){
		for(int j=1;j<=len;j++){
			if(i&(1<<(j-1))) continue;
			for(int k=0;k<d;k++){
				dp[i|(1<<(j-1))][(k*10+(ch[j]-'0'))%d]+=dp[i][k];
			}
		}
	}
	ans=dp[(1<<len)-1][0];
} 
int main(){
//	freopen("test.in","r",stdin);
	//freopen("ans.out","w",stdout);
	int t;scanf("%d",&t);inv[0]=1;
	for(int i=1;i<=10;i++) inv[i]=inv[i-1]*i;
	while(t--){
		ans=0;
		scanf("%s",ch+1);scanf("%lld",&d);
		len=strlen(ch+1);
		for(int i=1;i<=len;i++) cnt[ch[i]-'0']++;//记录相同数字个数 
		work();
		for(int i=1;i<=len;i++){
			ans/=inv[cnt[ch[i]-'0']];//除去这个数字的个数的阶乘 
			cnt[ch[i]-'0']=0;
		}
		printf("%lld\n",ans);
	}
}