[BZOJ1072][SCOI2007]排列perm（状压DP）

=== ===

这里放传送门

=== ===

题解

看到s这么小还是统计方案数那应该大概就是状压DP啦。 用f[S][i] 表示当前选中数字的状态为S，模d的余数是i的方案数，每次枚举一个没有用过的数字把它加到当前排列的尾部，新的余数就是(i*10+v)%d啦。最后的结果就是所有数都选中并且余数为0的方案。然而这样算出来的是带有重复方案的，原因是给定的字串中可能有重复数字。最后的结果要除以每个重复元素的个数的阶乘之积，就类似于有重复元素的排列问题。

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int T,s[15],len,d,f[1100][1100],cnt[10],sdf; int mul(int k){ int sum=1; for (int i=2;i<=k;i++) sum*=i; return sum; } int main() { scanf("%d",&T); for (int wer=1;wer<=T;wer++){ char c=getchar();len=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0'){ s[++len]=c-'0'; c=getchar(); } scanf("%d",&d); memset(f,0,sizeof(f)); f[0][0]=1; for (int i=0;i<=(1<<len)-1;i++) for (int j=0;j<d;j++) if (f[i][j]!=0) for (int k=1;k<=len;k++){ int t=1<<(k-1); if (!(i&t))//保证枚举的数都是没选过的 f[i|t][(j*10+s[k])%d]+=f[i][j]; } memset(cnt,0,sizeof(cnt)); for (int i=1;i<=len;i++) cnt[s[i]]++; sdf=1; for (int i=0;i<=9;i++) sdf*=mul(cnt[i]); printf("%d\n",f[(1<<len)-1][0]/sdf); } return 0; }