首页 > 代码库 > [bzoj1072][SCOI2007][排列perm] (状态压缩+数位dp+排列去重)
[bzoj1072][SCOI2007][排列perm] (状态压缩+数位dp+排列去重)
Description
给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能
被2整除，其中末位为2的有30种，末位为4的有60种。
Input
输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0, 1
, 2, 3, 4, 5, 6, 7, 8, 9.
Output
每个数据仅一行，表示能被d整除的排列的个数。
Sample Input
7000 1001 11234567890 1123434 21234 712345 1712345678 29
Sample Output
13362880090361398
HINT
在前三个例子中，排列分别有1, 3, 3628800种，它们都是1的倍数。
【限制】
100%的数据满足：s的长度不超过10, 1<=d<=1000, 1<=T<=15
Solution
考虑整除的性质
联想一下竖式除法，一个数n%d=x，那么(n*10+y)%d=(x*10+y)%d
这就是此题利用的原理
设状态为f[i][j]，i是一个二进制数，第i位的0或1代表给定的数串该位数是否被选了，j代表当前i状态下除d余j的方案总数
那么转移如下
f[i|(1<<k)][(j*10+str[k])%d]=f[i|(1<<k)][(j*10+str[k])%d]+f[i][j]
有序枚举即可
#include<stdio.h>#include<string.h>char s[11];int n,d,frac[11],T,f[1<<10][1001],cnt[11],a[11];int main(){ frac[0]=1; for(int i=1;i<=10;i++) frac[i]=frac[i-1]*i; scanf("%d",&T); while(T--){ memset(f,0,sizeof(f)); memset(cnt,0,sizeof(cnt)); scanf("%s%d",&s,&d); n=strlen(s); for(int i=0;i<n;i++) cnt[a[i]=s[i]-‘0‘]++; f[0][0]=1; for(int i=0;i<(1<<n);i++) for(int j=0;j<d;j++) for(int k=0;k<n;k++) if(!(i&(1<<k))) f[i|1<<k][(j*10+a[k])%d]+=f[i][j]; int ans=f[(1<<n)-1][0]; for(int i=0;i<10;i++) ans/=frac[cnt[i]]; printf("%d\n",ans); } return 0;}
[bzoj1072][SCOI2007][排列perm] (状态压缩+数位dp+排列去重)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。