【bzoj1072】[SCOI2007]排列perm

2015.06.11 11:04 Thu | 18次阅读 | 旧日oi | 固定链接 | 源码

Description

给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除(可以有前导0)。例如123434有90种排列能被2整除,其中末位为2的有30种,末位为4的有60种。
100%的数据满足:s的长度不超过10, 1<=d<=1000, 1<=T<=15
题解
裸爆搜可过,但是很不优雅是不是……所以考虑一下状压dp,dp[i][j]表示用得数字状态为i,mod d为j时的总方案数,转移的时候可以分别把每个选的数字看成最后一位,写起来也就是dp[i|(1<<k)][(j*10+a[k])%d]+=dp[i][j],但是如果有两个相同的数字比如112,就被算了两次,所以答案要除以每个数出现的次数的阶乘。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T,d,len,ans;
char s[15];
int a[15],num[10],dp[1030][1005];
int power[10]={1};
int main()
{
    cin>>T;
    for(int i=1;i<=10;i++) power[i]=power[i-1]*i;
    while(T--)
    {
        scanf("%s%d",s,&d);len=strlen(s);
        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));dp[0][0]=1;
        for(int i=0;i<len;i++) 
        {
            a[i]=s[i]-'0';
            num[a[i]]++;
        }
        for(int i=0;i<(1<<len);i++)
        for(int j=0;j<d;j++)
        if(dp[i][j])
        {
            for(int k=0;k<len;k++)
            if(!(i&(1<<k))) dp[i|(1<<k)][(j*10+a[k])%d]+=dp[i][j];
        }
        ans=dp[(1<<len)-1][0];
        for(int i=0;i<=9;i++) ans/=power[num[i]];
        printf("%d\n",ans);
    }
}```