[BZOJ 1072] 排列perm

Link：

BZOJ 1072 传送门

Solution：

一道直接next_permutation纯暴力就能过的题？

难道2007年时大家都不知道next_permutation这个函数吗

还是用复杂度更优的状压DP吧

设$dp[i][j]$为状态为$i$且对$d$余$j$的个数，

注意$dp[(1<<len)-1][0]$最后除去$\prod_{i=0}^9 cnt[i]!$，排除重复项

现在对状压DP状态的选取有了些感悟，

一般来说第一项表示状态，而第二项表示的一般都是于答案相关且包含答案情况的

（EX：求整除，表示当前对$d$的余数）

Code：

#include <bits/stdc++.h>

using namespace std;

int T,d,len,cnt[],dupli[],dp[][];

char s[];

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s %d",s,&d);len=strlen(s);

        for(int i=;i<;i++) dupli[i]=;

        memset(cnt,,sizeof(cnt));memset(dp,,sizeof(dp));

        for(int i=;i<len;i++)

            cnt[s[i]-'']++,dupli[s[i]-'']*=cnt[s[i]-''];

        dp[][]=;

        for(int i=;i<(<<len);i++)

            for(int j=;j<d;j++)

                if(dp[i][j])

                    for(int k=;k<len;k++)

                        if(!(i&(<<k)))

                            dp[i|(<<k)][(j*+(s[k]-''))%d]+=dp[i][j];

        for(int i=;i<=;i++) dp[(<<len)-][]/=dupli[i];

        printf("%d\n",dp[(<<len)-][]);

    }

    return ;

}

巴特西

[BZOJ 1072] 排列perm

Link：

Solution：

Code：

最新文章

热门文章