状压DP之排列perm

题目

[SCOI2007]排列

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

输入格式

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

输出格式

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

样例

样例输入

7

000 1

001 1

1234567890 1

123434 2

1234 7

12345 17

12345678 29

样例输出

数据范围与提示

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

100%的数据满足：s的长度不超过10, 1<=d<=1000, 1<=T<=15。

思路

这道题棘手的地方是如何将数转化为二进制数存储状态，所以，我们先不管他所在数位的具体数目是多少，用二进制记录状态（1代表有，0代表没有），就很明了了，再来考虑数的问题，开一个和原字符组长度相等的数组，记录相应数位的数大小，我们定义DP数组\(F[i][j]\)代表状态\(i\)下余数为\(j\)的排序个数，\(cnt[i]\)记录\(i\)出现次数（作用下文说明），用\(a[i]\)代表原字符串相应\(i-1\)位置上的数的大小;
接着我们在第一层枚举状态\(i\)，第二层枚举余数\(k\)，在此加判断，如果\(f[i][k]\)为0，不需要进行以下操作，为0叠加无效，第三层枚举在\(i\)状态后面插入的数字\(j\)，如果\(j\)位的数字没有出现，则进行转移 \(f[(i|(1<<j))][(k*10+a[j+1])%mod] += f[i][k]\),上一状态的最优借叠加上来。
还有一点就是数字重复，这时候就体现\(cnt\)的作用了，记录某个数字出现的次数，这些数字相互交换位置答案一样，对于数字\(i\)，出现\(cnt[i]\)次,那么有\(A^{cnt[i]}_{cnt[i]}\)重复,要用\(f[lim-1][0]\)除去,注意判零！！！（还有一种去重方法，详细见<刘某>）

上代码



#include<bits/stdc++.h>

using namespace std;

const int maxn=1<<11,maxm=1000+10;

int f[maxn][maxm];//f[i][j]表示状态i余数为j的排序个数

int T,mod;

int a[maxn],cnt[maxn];//cnt记录某个数i出现的次数

char s[15];

int J[]={0,1,2,6,24,120,720,5040,40320,362880,3628800};

int main(){

	scanf("%d",&T);

	while(T--){

		memset(cnt, 0, sizeof(cnt));//一定记得初始化

        memset(f, 0, sizeof(f));

		scanf("%s%d",s,&mod);

		int len=strlen(s);

		for(int i=0;i<len;i++){

			a[i+1]=s[i]-'0';

			cnt[a[i+1]]++;//记录a[i+1]出现次数

		}

		int lim=1<<len;//记录界限

		f[0][0]=1;//初始化临界状态，0状态下余数为0的有1种情况

		for(int i=0;i<lim;i++){//枚举状态

			for(int k=0;k<mod;k++){//枚举余数

				if(f[i][k]){//假如没有跳过

					 for(int j=0; j<len; j++)//枚举插入的数字

                   		               if( (i & (1<<j)) == 0 )//无交集

                                                      f[(i|(1<<j))][(k*10+a[j+1])%mod] += f[i][k];//叠加

				}

			}

		}

		int ans=f[lim-1][0];

		for(int i=0; i<=9; i++) if( cnt[i] ) ans /= J[cnt[i]];//去重

		cout<<ans<<endl;

	}

}

巴特西