P3977 [TJOI2015]棋盘
题目描述
为了提高智商,ZJY去新世界旅游了。可是旅游过后的ZJY杯具的发现要打开通往原来世界的门,必须要解开门上面画的谜题。谜题是这样的:有个n行m列的棋盘,棋盘上可以放许多特殊的棋子。每个棋子的攻击范围是3行,p列。输入数据用一个3×p的矩阵给出了棋子攻击范围的模板,棋子被默认为模板中的第1行,第k列,则棋子能攻击到的位置是1,不能攻击到的位置是0。1≤p≤m,0≤k<p。输入数据保证第1行第k列的位置是1。打开门的密码就是,在要求棋子互相不能攻击到的前提下,摆放棋子的方案数。注意什么棋子都不摆放也算作一种可行方案。由于方案数可能很大,而密码为32位的二进制密码,所以ZJY仅需要知道方案数对2的32次方取余数的结果即可。
输入格式
输入数据的第一行为两个整数n和m,表示棋盘的大小。第二行为两个整数p和k,表示接下来的攻击范围模板的大小,以及棋子在模板中的位置。接下来三行,每行有P个数,表示攻击范围的模版。每个数字后有一个空格。
输出格式
输出数据仅有一行,一个整数,表示可行的方案数模2^32的余数。
输入输出样例
输入 #1
5 5
3 1
0 1 0
1 1 1
0 1 0
输出 #1
55447
说明/提示
数据范围
对于10%的pn，1 ≤ n ≤ 5，1 ≤ m ≤ 5
对于50%的pn，1 ≤ n ≤ 1000，1 ≤ m ≤ 6
对于100%的pn，1 ≤ n ≤ 1000000，1 ≤ m ≤ 6
解法
80stp：
普通状压dp，把每行情况存储，逐行转移。复杂度O($n*2^m$)。
100stp:
我们发现每行转移与行的位置无关，所以可以用矩阵快速幂加速。
代码
80stp：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define ll long long
using namespace std;
int p, k;
int moban[3];
int end = 0;
ll dp[2][1 << 7];
int qk[1 << 7];
int gj[2][1 << 7];
vector<int> pr[1 << 7];
void inil(int js) {
js = (1 << js);
int now = 0;
while (now < js) {
bool flag = true;
for (int i = 0; (now >> i) > 0; ++i) {
if ((now >> i) & 1) {
if (i < k && (((moban[1] >> (k - i)) & now) != 0)) {
flag = false;
break;
} else if (((moban[1] << (i - k)) & now) != 0) {
flag = false;
break;
}
}
}
if (flag) {
qk[end] = now;
for (int i = 0; (now >> i) > 0; ++i) {
if ((now >> i) & 1) {
if (i < k) {
gj[0][end] |= (moban[0] >> (k - i));
gj[1][end] |= (moban[2] >> (k - i));
} else {
gj[0][end] |= (moban[0] << (i - k));
gj[1][end] |= (moban[2] << (i - k));
}
}
}
++end;
}
++now;
}
for (int i = 0; i < end; ++i) {
for (int j = 0; j < end; ++j) {
if ((gj[1][i] & qk[j]) == 0 && (gj[0][j] & qk[i]) == 0) {
pr[j].push_back(i);
}
}
}
return;
}
ll mod = 1;
int main() {
mod <<= 32;
int n, m;
scanf("%d%d", &n, &m);
scanf("%d%d", &p, &k);
k = p - k;
--k;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < p; ++j) {
moban[i] <<= 1;
int a;
scanf("%d", &a);
moban[i] += a;
}
}
moban[1] ^= (1 << k);
inil(m);
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < end; ++j) {
dp[i & 1][j] = 0;
int size = pr[j].size();
for (int k = 0; k < size; ++k) {
dp[i & 1][j] += dp[(i - 1) & 1][pr[j][k]];
dp[i & 1][j] %= mod;
}
}
}
ll ans = 0;
for (int i = 0; i < end; ++i) {
ans += dp[n & 1][i];
ans %= mod;
}
printf("%lld", ans);
return 0;
}
|
100stp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
| #include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define ll long long
#define ull unsigned long long
using namespace std;
int p, k;
int moban[3];
int end = 0;
int qk[1 << 7];
int gj[2][1 << 7];
vector<int> pr[1 << 7];
struct matrix {
ull num[1 << 7][1 << 7];
void inil() { memset(num, 0, sizeof(num)); }
void inil1() {
for (int i = 0; i < (1 << 7); ++i) {
num[i][i] = 1;
}
}
} yx;
ll mod = 1;
void inil(int js) {
js = (1 << js);
int now = 0;
while (now < js) {
bool flag = true;
for (int i = 0; (now >> i) > 0; ++i) {
if ((now >> i) & 1) {
if (i < k && (((moban[1] >> (k - i)) & now) != 0)) {
flag = false;
break;
} else if (((moban[1] << (i - k)) & now) != 0) {
flag = false;
break;
}
}
}
if (flag) {
qk[end] = now;
for (int i = 0; (now >> i) > 0; ++i) {
if ((now >> i) & 1) {
if (i < k) {
gj[0][end] |= (moban[0] >> (k - i));
gj[1][end] |= (moban[2] >> (k - i));
} else {
gj[0][end] |= (moban[0] << (i - k));
gj[1][end] |= (moban[2] << (i - k));
}
}
}
++end;
}
++now;
}
for (int i = 0; i < end; ++i) {
for (int j = 0; j < end; ++j) {
if ((gj[1][i] & qk[j]) == 0 && (gj[0][j] & qk[i]) == 0) {
yx.num[j][i] = 1;
}
}
}
return;
}
struct matrix mul(struct matrix a, struct matrix b) {
struct matrix ans;
ans.inil();
for (int i = 0; i <= end; ++i) {
for (int j = 0; j <= end; ++j) {
for (int k = 0; k <= end; ++k) {
a.num[i][k] %= mod;
b.num[k][j] %= mod;
ull temp = a.num[i][k] * b.num[k][j];
temp %= mod;
if (temp < 0) {
cout << a.num[i][k] << " " << b.num[k][j] << endl;
}
ans.num[i][j] += temp;
ans.num[i][j] %= mod;
}
}
}
return ans;
}
struct matrix jzksm(struct matrix a, int n) {
if (n == 1)
return a;
struct matrix ans;
ans.inil1();
while (n != 0) {
if (n & 1)
ans = mul(ans, a);
n >>= 1;
a = mul(a, a);
}
return ans;
}
int main() {
yx.inil();
mod <<= 32;
int n, m;
scanf("%d%d", &n, &m);
scanf("%d%d", &p, &k);
k = p - k;
--k;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < p; ++j) {
moban[i] <<= 1;
int a;
scanf("%d", &a);
moban[i] += a;
}
}
moban[1] ^= (1 << k);
inil(m);
yx = jzksm(yx, n);
ull ans = 0;
for (int i = 0; i < end; ++i) {
ans += yx.num[i][0];
ans %= mod;
}
printf("%lld", ans);
return 0;
}
|
