暑假集训Day 4 P4163 [SCOI2007]排列 (状压dp)

状压dp

(看到s的长度不超过10就很容易想到是状压dp了

但是这个题的状态转移方程比较特殊)

题目大意

给一个数字串 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 整除的排列的个数。

输入样例

7

000 1

001 1

1234567890 1

123434 2

1234 7

12345 17

12345678 29

输出样例

1

3

3628800

90

3

6

1398

算法分析

  • 这个题的思路还是蛮偏的,,,,但是很好理解

    我们将f数组的第一维定义为状态 (最大值为1<<10) 第二维定义为 余数

    那么问题就来了 如果我们把第一维定义为状态的话 应该是怎样的状态呢?

    还是一样举个栗子:

    给出的数为1234 我们就定义一个1<<4大小的状态 然后每一位表示对应该位置的数是否已经添加

    比如0101就表示此时我们已经添加了2和4还有1和3没有添加进去 下一次可以选择添加进去1或者3
  • 循环顺序

    第一层循环状态 第二层循环余数 第三层循环下一个添加的数字

    则转移方程就是f[i|1<<k][(j * 10+k)%d] += f[i][j]

    第一维是i|1<<k 显然就是加上k位置的数字

    第二维是(j * 10+k)%d 即上一位的余数再加上当前位 然后整个再%d

    *转移条件

    如果当前状态向下个状态转移的时候 即加上第k位置数字 这个已经转移过了 那么显然就不能再加一次了

    判断语句就是
if((i & (1<<k)) == 0)

此时状态为i 想要转移的状态为i|1<<k 如果i&1<<k != 0 即表示i在第k位为1 也就是表示这个状态已经转移过了 所以要保证==0的时候再转移

  • 需要注意有的数字是重复的 显然根据排列组合的规律 除以这个重复数字的全排列即可 即除以该数的阶乘(可以预处理或者写个函数 这里提供函数的代码)

代码展示



#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int f[1<<10][1001],T,a[maxn],d,cnt[11];
char s[maxn]; int jc(int x){
int u = 1;
for(int i = 1;i <= x;++i)u *= i;
return u;
} 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));
for(int i = 0;i < len;++i){
a[i] = s[i] - '0';
cnt[a[i]]++;
}
int maxs = (1<<len)-1;
f[0][0] = 1;
for(int i = 0;i <= maxs;++i){
for(int j = 0;j < d;++j)
if(f[i][j])
for(int k = 0;k < len;++k)
if((i & (1<<k)) == 0)
f[i|(1<<k)][(j*10+a[k])%d] += f[i][j];
}
int ans = f[maxs][0];
for(int i = 0;i <= 9;++i){
if(cnt[i]!=0)ans/=jc(cnt[i]);
}
printf("%d\n",ans);
}
return 0;
}

谢谢观看

点个关注>)<

上一篇:BZOJ 1072 [SCOI2007]安排perm 如压力DP


下一篇:S-CMS企业建站v3几处SQL注入