首页 > 代码库 > [BZOJ 1072] [SCOI2007] 排列perm 【状压DP】
[BZOJ 1072] [SCOI2007] 排列perm 【状压DP】
题目链接：BZOJ 1072
这道题使用 C++ STL 的 next_permutation() 函数直接暴力就可以AC 。（使用 Set 判断是否重复）
代码如下：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <set>using namespace std;int T, d, l, Ans;int A[15];char Str[15];typedef long long LL;LL Num;set<LL> S;int main() { scanf("%d", &T); for (int Case = 1; Case <= T; Case++) { scanf("%s%d", Str, &d); Ans = 0; S.clear(); l = strlen(Str); for (int i = 0; i < l; i++) A[i] = Str[i] - ‘0‘; sort(A, A + l); while (true) { Num = 0; for (int j = 0; j < l; j++) Num = Num * 10 + A[j]; if (S.count(Num) == 0 && Num % d == 0) { ++Ans; S.insert(Num); } if (!next_permutation(A, A + l)) break; } printf("%d\n", Ans); } return 0;}
但是比较慢，正常一点的解法应该是使用状压 DP 。
设定一个状态 f[i][j] ，其中 i 的二进制表示当前已经使用了原数串中的某些位 (在 i 中为 1 的位) ，j 表示当前的数字 mod 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])! （排列数）。
代码如下：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>using namespace std;int T, d, l, Ans;int A[15], Cnt[15], f[1024 + 5][1000 + 5];char Str[15];int main() { scanf("%d", &T); for (int Case = 1; Case <= T; Case++) { scanf("%s%d", Str, &d); l = strlen(Str); memset(Cnt, 0, sizeof(Cnt)); for (int i = 0; i < l; i++) { A[i] = Str[i] - ‘0‘; ++Cnt[A[i]]; } memset(f, 0, sizeof(f)); f[0][0] = 1; for (int i = 0; i < (1 << l); i++) { for (int j = 0; j < d; j++) { for (int k = 0; k < l; k++) { if ((i & (1 << k)) == 0) f[i | (1 << k)][(j * 10 + A[k]) % d] += f[i][j]; } } } Ans = f[(1 << l) - 1][0]; for (int i = 0; i <= 9; i++) { for (int j = 1; j <= Cnt[i]; j++) { Ans /= j; } } printf("%d\n", Ans); } return 0;}
[BZOJ 1072] [SCOI2007] 排列perm 【状压DP】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。