【BZOJ4000】【LOJ2104】【TJOI2015】棋盘 (状压dp + 矩阵快速幂)

Description

有一个\(~n~\)行\(~m~\)列的棋盘，棋盘上可以放很多棋子，每个棋子的攻击范围有\(~3~\)行\(~p~\)列。用一个\(~3 \times p~\)的矩阵给出了棋子攻击范围的模板，棋子被默认在模板中的第一行，第\(~k~\)列，模板中棋子能攻击到的位置标记为\(~1\)，不能攻击到的位置是\(~0\) 。输入数据保证模板中的第二行第\(~k~\)列是\(~1\)。在要求棋子互相不能攻击到的前提下，求摆放棋子的方案数。

\(~1 \leq p \leq m,~ 1 \leq k \leq p, ~1 \leq n \leq {10 ^ 6}~, ~1 \leq m \leq 6~\).

看原题戳我

Solution

对于这个“要求棋子互相不能攻击到的前提下”的约束条件，先考虑普通\(~dp~\)转移，记\(~dp_{i,~j}~\)表示第\(~i~\)行状态为\(~j~\)的方案书，可以发现\(~dp_i~\)的某些状态是从\(~dp_{i - 1}~\)的合法状态转移而来的。但这样的话对于\(~dp_i~\)要枚举\(~dp_{i - 1}~\)和\(~dp_i~\)的合法状态，时间复杂度\(~O({2^ {2m}}n)~\)，显然不行。

发现从\(~dp_i~\)转移到\(~dp_{i + 1}~\)的方式是一样的，考虑矩阵快速幂加速，枚举任意两个状态并判断其是否可以转移即可，可以转移当且仅当在两行的任意\(~1~\)的位置放棋子都不会攻击到其他任意一个棋子。

要注意的是这题的下标全是从\(~0~\)开始的。。。

Code

#include<bits/stdc++.h>

#define Set(a, b) memset(a, b, sizeof (a))

#define For(i, j, k) for(int i = j; i <= k; ++i)

using namespace std;

inline int read() {

	int x = 0, p = 1; char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') p = -1;

	for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

	return x *= p;

}

inline void File() {

#ifndef ONLINE_JUDGE

	freopen("bzoj4000.in", "r", stdin);

	freopen("bzoj4000.out", "w", stdout);

#endif

}

const int N = (1 << 6) + 5;

typedef unsigned int uint;

struct matrix { uint a[N][N]; } a, b;

int n, m, p, k, atk[3], all, now;

inline matrix operator * (const matrix a, const matrix b) {

	matrix c; Set(c.a, 0);

	For(i, 0, all) For(k, 0, all) For(j, 0, all)

		c.a[i][j] += a.a[i][k] * b.a[k][j];

	return c;

}

inline matrix qpow(matrix a, int b) {

	matrix res; For(i, 0, all) res.a[i][i] = 1;

	for (; b; a = a * a, b >>= 1) if (b & 1) res = res * a;

	return res;

}

inline bool check(int st1, int st2) {

	For(i, 0, m - 1) if (st1 & (1 << i)) {

		if (i > k) now = atk[1] << (i - k); else now = atk[1] >> (k - i);

		if ((now & st1) != (1 << i)) return false;

	}

	For(i, 0, m - 1) if (st2 & (1 << i)) {

		if (i > k) now = atk[1] << (i - k); else now = atk[1] >> (k - i);

		if ((now & st2) != (1 << i)) return false;

	}

	For(i, 0, m - 1) if (st1 & (1 << i)) {

		if (i > k) now = atk[2] << (i - k); else now = atk[2] >> (k - i);

		if (now & st2) return false;

	}

	For(i, 0, m - 1) if (st2 & (1 << i)) {

		if (i > k) now = atk[0] << (i - k); else now = atk[0] >> (k - i);

		if (now & st1) return false;

	}

	return true;

}

int main() {

	File();

	cin >> n >> m >> p >> k;

	For(i, 0, 2) For(j, 0, p - 1) atk[i] |= (read() << j);

	all = (1 << m) - 1;

	For(s, 0, all) For(t, 0, all) if (check(s, t)) a.a[t][s] = 1;

	For(i, 0, all) b.a[i][0] = 1;

	b = qpow(a, n - 1) * b;

	uint ans = 0;

	For(i, 0, all) ans += b.a[i][0];

	printf("%u", ans);

	return 0;

}

巴特西

【BZOJ4000】【LOJ2104】【TJOI2015】棋盘 (状压dp + 矩阵快速幂)

Description

Solution

Code

最新文章

热门文章