洛谷4163 [SCOI2007]排列

题意

给一个数字串 $s(|s|\le 10)$ 和正整数 $d(\le 1000)$ , 统计 $s$ 有多少种不同的排列能被 $d$ 整除（可以有前导 $0$）。

题解

$|s|$ 较小，考虑状压。用 $f(S,i)$ 表示下标集合 $S$ 内的数都用过了，当前数 $\equiv i\pmod d$ 。每次枚举一个不在 $S$ 的数 $j$ 加入转移，方程式为：

$$f(S,i)\rightarrow f(S\cup j,(i\times 10+s_j)\mod d)$$

但还有一个问题，如果有多个相同的数，答案中就会包含重复的排列。可以用排列组合原理去重，如果数字 $i$ 有 $cnt[i]$ 个，那么答案就需要 $\div cnt[i]!$ 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

char s[15];
int t,d,n,fac[15],cnt[10],f[1<<11][1005];

signed main()
{
    fac[0]=1;
    for (int i=1;i<=10;i++) fac[i]=fac[i-1]*i;
    t=read();
    while (t--)
    {
        memset(f,0,sizeof(f));
        memset(cnt,0,sizeof(cnt));
        scanf("%s",s); d=read();
        n=strlen(s);
        for (int i=0;i<n;i++) s[i]-='0',cnt[int(s[i])]++;
        const int N=1<<n;
        f[0][0]=1;
        for (int i=0;i<N;i++)
        {
            for (int j=0;j<n;j++)
            {
                if (i>>j&1) continue;
                for (int k=0;k<d;k++) f[i|(1<<j)][(k*10+s[j])%d]+=f[i][k];
            }
        }
        int ans=f[N-1][0];
        for (int i=0;i<=9;i++) ans/=fac[cnt[i]]; //去重
        printf("%d\n",ans);
    }
    return 0;
}