[SCOI2007]排列

标签：动态规划 状态压缩

---

题目描述

给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能被2整除，其中末位为2的有30种，末位为4的有60种。

输入输出格式

输入格式：

输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0, 1
, 2, 3, 4, 5, 6, 7, 8, 9.

输出格式：

每个数据仅一行，表示能被d整除的排列的个数。

输入输出样例

输入样例#1：
7
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29

输出样例#1：
1
3
3628800
90
3
6
1398

HINT
在前三个例子中，排列分别有1, 3, 3628800种，它们都是1的倍数。

说明

100%的数据满足：s的长度不超过10, 1<=d<=1000, 1<=T<=15

题解

首先看到s很小，所以我们可以把s的状态压缩起来，题目还涉及是d的倍数，所以还需要一维记录余数。
设f[i][j]表示状态为i时余数为j的方案数。
那么每次枚举一个数，如果这个数没在i中出现过，就把他放到末尾（也可以放到首位，不过处理起来相对麻烦一些），并更新状态。

f[i | (1 << k)][(j * 10 + num[k]) % d] += f[i][j];

需要注意的是，因为数字有重复现象，所以我们最后答案要对每一个数字除以cnt[i]!
cnt[i]表示数字i出现的个数
当然这道题数据太小以至于可以用搜索。在此就不过多赘述了。

代码

#include<bits/stdc++.h>
#define N 2010
using namespace std;

char s[N];
int t, d;
int f[N][N], num[N], cnt[N];

int calc(int x)
{
    int ans = 1;
    for(int i = 1; i <= x; i ++) ans *= i;
    return ans;
}

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        scanf("%s%d", s, &d);
        int len = strlen(s);
        memset(cnt, 0, sizeof(cnt));
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for(int i = 0; i < len; i ++)
        {
            num[i] = s[i] - '0';
            cnt[s[i] - '0'] ++;
        }
        for(int i = 0; i < (1 << len); i ++)
            for(int j = 0; j <= d; j ++)
                for(int k = 0; k < len; k ++)
                    if(!(i & (1 << k)))
                       f[i | (1 << k)][(j * 10 + num[k]) % d] += f[i][j];
        for(int i = 0; i < 10; i ++)
            f[(1 << len) - 1][0] /= calc(cnt[i]);
        printf("%d\n", f[(1 << len) - 1][0]);
    } 
    return 0;
} 

心得

一般涉及倍数或者余数的问题，都要新开一维来记录状态。