P4163

Aryper · 2021-08-21 17:32:44 · 个人记录

[SCOI2007]排列

据说是套路。

定义状态 f[i][j] 表示选数状态为 i 时，余数为 j 的排列方案数。

然后我们可以这样递推：

简单来说，加入了第 i 位的数 a[j]，并且要把这个数放在最后（因为其他状态的转移会把 a[j] 前置的情况考虑到），然后就会使之前的余数乘 10，再加上这个 a[j] 就是新的余数。

另外，对于重复的数字，我们重复计入了它们的全排列。

对于最后的答案，若数字 i 出现了 cnt 次，我们使 f[(1<<len)-1][0]=\dfrac{f[(1<<len)-1][0]}{cnt!}。

这样我们就可以不重不漏的统计所有的答案了。

时间复杂度 O(Td|s|\cdot2^{|s|})。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstring>
#define ll long long
using namespace std;

const ll N=12,D=1e3;

ll T,d,len;

char s[N+5];

ll f[(1<<N)+5][D+5],a[N+5],fac[N+5],cnt[N+5];

void init() {
    fac[0]=1;
    for(ll i=1;i<=10;i++) {
        fac[i]=fac[i-1]*i;
    }
}

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

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    init();

    T=read();

    while(T--) {
        memset(f,0,sizeof(f));
        memset(cnt,0,sizeof(cnt));
        cin>>s;d=read();len=strlen(s);
        for(ll i=0;i<len;i++) {
            a[i+1]=s[i]-48;cnt[a[i+1]]++;
        }
        f[0][0]=1;
        for(ll i=0;i<(1<<len);i++) {
            for(ll j=1;j<=len;j++) if(!(i&(1<<(j-1)))) {
                for(ll k=0;k<d;k++) {
                    f[i|(1<<(j-1))][(k*10+a[j])%d]+=f[i][k];
                }
            }
        }
    //  printf("test:%lld\n",f[(1<<len)-1][0]);
        for(ll i=0;i<=9;i++) {
            f[(1<<len)-1][0]/=fac[cnt[i]];
        //  printf("fac[%lld]=%lld\n",cnt[i],fac[cnt[i]]);
        }
        write(f[(1<<len)-1][0]);putchar('\n');
    }

    return 0;
}