bzoj 1072 排列

Written with StackEdit.

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

HINT

在前三个例子中，排列分别有(1, 3, 3628800)种，它们都是(1)的倍数。

(s)的长度不超过(10, 1<=d<=1000, 1<=T<=15.)

Solution

开始觉得就是个弱智(dfs),写了一发,结果(T)了.
吓得我去写状压(dp),然后想的时候发现(dfs)是可以做的.只是我第一次的枚举姿势不对...

• (dfs)过程中传递余数(r),枚举的时候直接枚举填入(0)~(9)的哪一个数字,预处理每种数字的个数即可.
• 开始的时候我是枚举的填入串中的第几个数字,算阶乘去重把我卡(T)了.

#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=11;
int vis[MAXN];
int ans=0;
char s[MAXN];
int d,n;
int t[MAXN];
void dfs(int k,int r)
{
	if(k>n)
		{
			ans+=(r==0);
			return;
		}
	for(register int i=0;i<=9;++i)
		{
			if(t[i])
				{
					--t[i];
					dfs(k+1,(r*10+i)%d);
					++t[i];
				}
		}
}
int main()
{
	int T=read();
	while(T--)
		{
			scanf("%s",s+1);
			n=strlen(s+1);
			d=read();
			memset(t,0,sizeof t);
			for(register int i=1;i<=n;++i)
				++t[s[i]-'0'];
			ans=0;
			dfs(1,0);
			printf("%d
",ans);				
		}
	return 0;
}