bzoj 1072: [SCOI2007]排列perm【状压dp】

时间：2024-12-01 08:36:49

先写了个next_permutation结果T了，于是开始写状压

设f[s][i]为选取状态为s，选的数模d为i的方案数，去重的话直接除以每个数字的出现次数的阶乘即可

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=20;

int T,d,n,a[N],fac[N],c[N],f[2005][2005];

char s[N];

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		scanf("%s%d",s+1,&d);

		n=strlen(s+1);

		for(int i=0;i<=9;i++)

			fac[i]=1,c[i]=0;

		for(int i=1;i<=n;i++)

		{

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

			c[a[i]]++;

			fac[a[i]]*=c[a[i]];

		}

		for(int i=0;i<(1<<n);i++)

			for(int k=0;k<d;k++)

				f[i][k]=0;

		f[0][0]=1;

		for(int i=0;i<(1<<n);i++)

			for(int j=0;j<d;j++)

				for(int k=1;k<=n;k++)

					if(!((1<<(k-1))&i))

						f[i|(1<<(k-1))][(a[k]+j*10)%d]+=f[i][j];

		for(int i=0;i<=9;i++)

			f[(1<<n)-1][0]/=fac[i];

		printf("%d\n",f[(1<<n)-1][0]);

	}

	return 0;

}

相关文章