[bzoj1072] [SCOI2007]排列perm

Description

　　给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。

Input

　　输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Output

　　每个数据仅一行，表示能被d整除的排列的个数。

Sample Input

7
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29

Sample Output

1
3
3628800
90
3
6
1398

Solution

直接爆搜即可。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}

const int maxn = 2e5+10;

#define ll long long 

char s[20];int ans,d,n,num[20];

void dfs(int w,ll x) {
	if(w==n+1) {if(x%d==0) ans++;return ;}
	for(int i=0;i<10;i++) if(num[i]) num[i]--,dfs(w+1,1ll*x*10+i),num[i]++;
}

int main() {
	int T;read(T);
	for(int i=1;i<=T;i++) {
		memset(num,0,sizeof num);
		ans=0;scanf("%s",s+1);read(d);n=strlen(s+1);
		for(int j=1;j<=n;j++) num[s[j]-'0']++;
		dfs(1,0);write(ans);
	}
	return 0;
}