狀壓dp, 然后轉移都是一樣的, 矩陣乘法+快速冪就行啦. O(logN*2^(3m))?

---------------------------------------------------------------------------------------------

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define b(x) (1 << (x))typedef unsigned int matrix[100][100];const int maxn = 9;bool OK[b(maxn)];int N, n, U, M, D, p, k;matrix Q, res, mat;void Init() {scanf("%d%d%d%d", &N, &n, &p, &k);U = M = D = 0;for(int i = 0; i < p; i++) {int v; scanf("%d", &v);if(v) U |= b(i);}for(int i = 0; i < p; i++) {int v; scanf("%d", &v);if(v) M |= b(i);}for(int i = 0; i < p; i++) {int v; scanf("%d", &v);if(v) D |= b(i);}M ^= b(k);}bool chk(int x) {for(int i = 0; i < n; i++) if(x & b(i)) {if(i <= k && ((M >> (k - i)) & x)) return 0;if(i > k && ((M << (i - k)) & x)) return 0;}return true;}unsigned int Jud(int x, int y) {for(int i = 0; i < n; i++) {if(b(i) & x) {if(i <= k && ((D >> (k - i)) & y)) return 0U;if(i > k && ((D << (i - k)) & y)) return 0U;}if(b(i) & y) {if(i <= k && ((U >> (k - i)) & x)) return 0U;if(i > k && ((U << (i - k)) & x)) return 0U;}}return 1U;}void Work() {for(int s = b(n); s--; ) OK[s] = chk(s);for(int i = b(n); i--; ) if(OK[i])for(int j = b(n); j--; ) if(OK[j])Q[j][i] = Jud(i, j);for(int i = b(n); i--; ) res[i][i] = 1U;for(N--; N; N >>= 1) {if(N & 1) {for(int i = b(n); i--; )for(int j = b(n); j--; ) {mat[i][j] = res[i][j];res[i][j] = 0;}for(int k = b(n); k--; )for(int i = b(n); i--; )for(int j = b(n); j--; )res[i][j] += Q[i][k] * mat[k][j];}for(int i = b(n); i--; )for(int j = b(n); j--; ) {mat[i][j] = Q[i][j];Q[i][j] = 0;}for(int k = b(n); k--; )for(int i = b(n); i--; )for(int j = b(n); j--; )Q[i][j] += mat[i][k] * mat[k][j];}unsigned int ans = 0;for(int i = b(n); i--; ) if(OK[i])for(int j = b(n); j--; ) if(OK[j])ans += res[i][j];printf("%u\n", ans);}int main() {Init();Work();return 0;}

---------------------------------------------------------------------------------------------?

4000: [TJOI2015]棋盤

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?355??Solved:?159
[Submit][Status][Discuss]

Description

?

Input

輸入數據的第一行為兩個整數N，M表示棋盤大小。第二行為兩個整數P，K，表示攻擊范圍模板的大小，以及棋子在模板中的位置。接下來三行，每行P個數，表示攻擊范圍的模版。每個數字后面一個空格。

Output

?一個整數，表示可行方案Mod 2 ^32

Sample Input

2 2
3 1
0 1 0
1 1 1
0 1 0

Sample Output

7

HINT

?1<=N<=10^6,1<=M<=6

Source

?

轉載于:https://www.cnblogs.com/JSZX11556/p/5156798.html

總結

以上是生活随笔為你收集整理的BZOJ 4000: [TJOI2015]棋盘( 状压dp + 矩阵快速幂 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。