BZOJ 1072: [SCOI2007]排列perm(状压DP/方案DP/STL)

Description

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

Input

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

Output

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

Sample Input

7
000 1
001 1
1234567890 1
123434 2
1234 7
12345 17
12345678 29

Sample Output

1
3
3628800
90
3
6
1398

HINT

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

【限制】

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

Source

Solution

暴力(也能AC):

直接用next_premutation暴力枚举,判重用set即可

DP:

Re

next_permutation比较慢,正常一点的解法应该是使用状压 DP 。

设定一个状态 \(f[i][j]\),其中\(i\)的二进制表示当前已经使用了原数串中的某些位 (在\( i \)中为\(1\)的位) ,\(j\)表示当前的数字 \(%d\) 的值。 \(f[i][j] \)表示达到这个状态的方案数。

那么状态转移就是 :\( f[i | (1<<k)][(j * 10 + A[k]) % d] += f[i][j]\)    \(((i \& (1<<k)) == 0) \)

由于原排列中的数字可能有重复的,所以我们计算了很多重复的方案数。

如果某个数字 \( i \)在排列中出现了\( Cnt[i] \)次,那么最后的答案\(Ans\)应该\(Ans/=(Cnt[i])! \)(排列数)。

 

0 0 vote
Article Rating
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments