自动搬运

查看原文

来自洛谷，原作者为

	Monster_Qi **

搬运于2025-08-24 21:57:12，当前版本为作者最后更新于2018-09-29 17:42:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

首先我们发现这道题s的长度很小，所以考虑点暴力的做法，状压dp或搜索。本蒟蒻搜索永远调不对，所以就写了个状压dp。因为所有s里的数都要出现一次，并且最后的答案是要求整除，那么我们设$dp[S][k]$表示现在所选的状态集合为S，当前所选的数组成的数字对d取余后的值为k，这样就可以转移了。首先枚举所有的状态S，然后再枚举所有没有被选的数j，再枚举余数k即可转移。
　　转移方程为：$dp[S|(1<<(j-1))][(k*10+a[j])\%d]+=dp[S][k]$;但是这样写是错误的，因为没有考虑重复的排列，比如说s为"001"，结果发现“010”这个状态会被算两次。。看到有大佬直接用数学方法去重orz，本蒟蒻不太会，就记了个临时数组$b[i]$，表示当前要填的数字i有没有被填过，这样就可以避免一个位置放相同元素的情况了，具体看代码。时间复杂度为$O(T*len*d*2^{len})$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
const int MAXN = 11;

int T,d,a[MAXN],cnt,dp[1<<MAXN][1002];
bool b[MAXN];
char s[MAXN];

int main(){
	scanf("%d",&T);int len;
	while(T--){
		memset(dp,0,sizeof(dp));
		scanf("%s%d",s+1,&d);
		len=strlen(s+1);cnt=0;
		for(register int i=1;i<=len;i++) a[i]=s[i]-'0';//把所有数字存一下
		dp[0][0]=1;  //赋初值
		for(register int S=0;S<(1<<len)-1;S++){ //S表示当前所选的状态集合
			memset(b,0,sizeof(b));  //注意清零
			for(register int j=1;j<=len;j++)if(!(S&(1<<(j-1))) && !b[a[j]]){ //如果a[j]已经转移过就不能继续转移了,j表示遍历s中的各位数字。
				b[a[j]]=1;
				for(register int k=0;k<d;k++) //k表示对d取余后的数
					dp[S|(1<<(j-1))][(k*10+a[j])%d]+=dp[S][k];
			}
		}
		printf("%d\n",dp[(1<<len)-1][0]);
	}
	return 0;
}