首页 > 代码库 > [BZOJ 2004] [Hnoi2010] Bus 公交线路 【状压DP + 矩阵乘法】
[BZOJ 2004] [Hnoi2010] Bus 公交线路 【状压DP + 矩阵乘法】
题目链接： BZOJ - 2004
题目分析
看到题目完全不会。。于是立即看神犇们的题解。
由于 p<=10 ，所以想到是使用状压。将每个连续的 p 个位置压缩成一个 p 位 2 进制数，其中共有 k 位是1，表示这 k 个位置是某辆 Bus 当前停下的位置。需要注意的是，每个状态的第一位必须是 1 ，这样保证了不会有重复的状态。 每个状态可以转移到右边的某些状态（由当前状态的第一个 1 移动）。初始状态和终止状态都是前面 k 位是 1 。用矩阵转移 n - k 次。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxMap = 130 + 5, Mod = 30031;int N, K, P, Top, Rec;int L[MaxMap];int Calc(int Num) { int Cnt = 0; while (Num) { ++Cnt; Num -= Num & -Num; } return Cnt;}bool Check(int x, int y) { x = (x - (1 << (P - 1))) << 1; int t = x ^ y; if (t - (t & -t) == 0) return true; return false;}struct Matrix { int x, y, Num[MaxMap][MaxMap]; void SetXY(int a, int b) { x = a; y = b; } void Clear(int xx) { for (int i = 1; i <= x; ++i) { for (int j = 1; j <= y; ++j) { Num[i][j] = xx; } } }} M0, MZ;Matrix Mul(Matrix A, Matrix B) { Matrix ret; ret.SetXY(A.x, B.y); ret.Clear(0); for (int i = 1; i <= ret.x; ++i) { for (int j = 1; j <= ret.y; ++j) { for (int k = 1; k <= A.y; ++k) { ret.Num[i][j] += A.Num[i][k] * B.Num[k][j]; ret.Num[i][j] %= Mod; } } } return ret;}Matrix Pow(Matrix A, int b) { Matrix ret, f; f = A; ret.SetXY(f.x, f.y); ret.Clear(0); for (int i = 1; i <= ret.x; ++i) ret.Num[i][i] = 1; while (b) { if (b & 1) ret = Mul(ret, f); b >>= 1; f = Mul(f, f); } return ret;}int main() { scanf("%d%d%d", &N, &K, &P); Top = 0; for (int i = (1 << (P - 1)); i <= (1 << P) - 1; ++i) { if (Calc(i) == K) { L[++Top] = i; if (i == (1 << P) - 1 - ((1 << (P - K)) - 1)) Rec = Top; } } MZ.SetXY(Top, Top); MZ.Clear(0); M0.SetXY(1, Top); M0.Clear(0); M0.Num[1][Rec] = 1; for (int i = 1; i <= Top; ++i) { for (int j = 1; j <= Top; ++j) { if (Check(L[i], L[j])) MZ.Num[i][j] = 1; } } MZ = Pow(MZ, N - K); M0 = Mul(M0, MZ); printf("%d\n", M0.Num[1][Rec]); return 0; }
[BZOJ 2004] [Hnoi2010] Bus 公交线路 【状压DP + 矩阵乘法】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。