bzoj1027 状压dp

https://www.lydsy.com/JudgeOnline/problem.php?id=1072

题意给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除

试了一下发现暴力可过

因为s的长度只有10的缘故，我们考虑用dp[i][j]来记录i状态下余数为j的数量。

i表示的是这个数字串中已经加入的数字，直接从前往后递推即可。

本题第一个难点在于想到用状压dp去做，第二个难点在于因为其中有相同的数字的缘故，算完了之后的答案需要用排列组合去重。

原本我觉得这样的状态无法表示每个元素加入的先后次序，后来发现每个dp状态的与下一个状态相关的只有余数，与加入的i先后状态无关，所以我们只需要考虑这个数选了没有即可

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,tmp,K;

inline int read()

{

   int now=;register char c=getchar();

   for(;!isdigit(c);c=getchar());

   for(;isdigit(c);now=now*+c-'',c=getchar());

   return now;

}

char str[maxn];

int a[maxn];

int d;

int ans;

int num[maxn];

LL dp[][];

const int C[] = {,,,,,,,,,,,};

int main()

{

    int T; Sca(T);

    while(T--){

        Mem(num,); ans = ;

        scanf("%s%d",str,&d);

        N = strlen(str);

        for(int i =  ; i < N ; i ++){

            a[i] = str[i] - '';

            num[a[i]]++;

        }

        Mem(dp,);

        dp[][] = ;

        for(int i =  ; i < ( << N); i ++){

            for(int j = ; j < N ; j++){

                if(i & ( << j)){

                    for(int k =  ; k < d; k ++){

                        dp[i][(k *  + a[j]) % d] += dp[i ^ ( << j)][k];

                    }

                }

            }

        }

        LL ans = dp[( << N) - ][];

        For(i,,){

            if(num[i]) ans /= C[num[i]];

        }

        Prl(ans);

    }

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

相关文章