题解 P4163 【[SCOI2007]排列】

· · 题解

解题思路

　　首先我们发现这道题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;
}