A simple Blog for wyx I've been down the bottle hoping.
BZOJ1072 排列perm 状压dp
发表于: | 分类: Oi | 评论:0 | 阅读:49

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

整除而且除数小,考虑在模意义下的运算
然后发现这玩意个数比较少,然后就压一下
$F(sta,j)$表示选的数字的状态为$sta$,算出来的数字$mod \quad d = j$的方案数,枚举下一个数字处理一下余数就行了
时间复杂度大概是 $O(2^s*d)$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int Maxn = 1<<11;
const int N = 1000+5;
typedef long long LL;
using namespace std;

LL F[Maxn][N];
int a[20],cnt;

int fac[N];

int main()
{
    fac[0] = 1;
    for(int i=1;i<=10;++i) fac[i] = fac[i-1] * i;
    int T ; 
    cin >> T;
    while(T--)
    {
        memset(F,0,sizeof F);
        memset(a,0,sizeof a);
        cnt = 0;
        char str[12];int d;
        scanf("%s%d",str,&d);
        int len = strlen(str); cnt = len;
        for(int i=0;i<len;++i) a[i+1] = str[i] - '0';
        F[0][0] = 1; 
        int Max = (1<<cnt) - 1;
        for(int i=0;i<=Max;++i)
            for(int k=0;k<d;++k)
                for(int j=1;j<=cnt;++j)
                {
                    if((1<<(j-1))&i) continue;
                    int tt = ((k<<1) + (k<<3) + a[j]) %d;
                    F[(1<<(j-1))|i][tt] += F[i][k];
                }
        int Times[11] = {};
        for(int i=1;i<=cnt;++i) Times[a[i]] ++;
        for(int i=0;i<=9;++i) F[Max][0] /= fac[Times[i]];
        cout << F[Max][0] << endl;
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP