SCOI2007 排列

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2007 排列

Date: Wed Sep 05 08:27:33 CST 2018

In Category: NoCategory

Description：

给一个数字串 $s$ 和一个数字 $d$ ，计算 $s$ 有多少种不同的排列能被 $d$ 整除，可以有前导零。

$1\le len_s\le 10,1\le d \le 1000$

Solution：

$s$ 长度只有 $10$ 可以状压， $f[i][j]$ 表示已经选的状态是 $i$ ，对 $d$ 取模余数是 $j$ 的方案数。转移直接枚举最后一位填哪个，注意如果这个数字已经选过就不能再选。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int f[1050][1010];

char c[12];

int m;

bool v[10];

void work()

{

    scanf("%s",c + 1);scanf("%d",&m);

    int n = strlen(c + 1);

    for(int i = 1;i <= n;++i)c[i] -= '0';

    int tot = (1 << n) - 1;

    memset(f,0,sizeof(f));

    f[0][0] = 1;

    for(int b = 0;b <= tot;++b)

    {

        memset(v,false,sizeof(v));

        for(int i = 1;i <= n;++i)

        {

            if(b & (1 << (i - 1)))continue;

            if(v[c[i]])continue;

            for(int k = 0;k < m;++k)

            {

                f[b | (1 << (i - 1))][(k * 10 + c[i]) % m] += f[b][k];

            }

            v[c[i]] = true;

        }

    }

    cout << f[tot][0] << endl;

    return;

}

int main()

{

    int testcases;

    scanf("%d",&testcases);

    while(testcases--)work();

    return 0;

}

In tag: DP-状压DP

wjh15101051