BZOJ 1072: [SCOI2007]排列perm（状压DP）

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整除的排列的个数。

题解：

看数据就知道很明显的状压DP

设dp[S][r]表示当前用过的数字的集合为S，对n的余数为r的方案数

注意一下，如果一个数字出现了cnt次，那么这个数字最后也一定用了cnt次，那么这样的答案就会被多次计算，因为我们状态sta的来源就有多个了，但是它们最后形成的数字是一样的，而每个这样出现了多次的数，都会造成cnt！种情况，而我们只需要一种，所以最后除以cnt！即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
const int MAXN = (1<<10)+20;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int dp[MAXN][MAXN],cnt[15]; char s[15];
signed main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
	int T; scanf("%d",&T);
	while(T--){
        int n; scanf("%s%d",s,&n);
        int m = strlen(s);
        memset(dp,0,sizeof(dp)); memset(cnt,0,sizeof(cnt));
        for(int i=0;i<m;i++) cnt[s[i]-'0']++;
        dp[0][0]=1;
        for(int i=0;i<(1<<m);i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<m;k++)
                    if(!(i&(1<<k)))
                        dp[i|(1<<k)][(j*10+s[k]-'0')%n]+=dp[i][j];
        int ans = dp[(1<<m)-1][0];
        for(int i=0;i<=9;i++)
            for(int j=2;j<=cnt[i];j++)
                ans/=j;
        printf("%d\n",ans);
	}
	return 0;
}