blob: 023ce6b6a8f3cd52f8c719a6aa4aadc0ec3ffd25 (
plain)
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
|
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
const int MX = 18;
int A[MX][MX];
ll B[1<<MX], DP[1<<MX], cnt[1<<MX][MX][MX];
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
int x; cin >> x;
A[i][x-1] = j;
}
}
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) if (i != j && A[j][i] <= A[j][j])
cnt[1<<i|1<<j][i][j] = 1;
for (int m = 0; m < 1<<N; ++m) {
for (int i = 0; i < N; ++i) if (m&1<<i) {
for (int j = 0; j < N; ++j) if (i != j && m&1<<j) {
if (A[i][j] <= A[i][i]) B[m] += cnt[m][i][j];
for (int k = 0; k < N; ++k) if (!(m&1<<k) && A[k][j] <= A[k][k])
cnt[m|1<<k][i][k] += cnt[m][i][j];
}
}
}
for (int m = 1; m < 1<<N; ++m) {
B[m] /= __builtin_popcount(m);
if (__builtin_popcount(m) == 1) ++B[m];
DP[m] = B[m];
}
for (int m = 0; m < 1<<N; ++m)
for(int i = m; i; i = i-1&m)
if (__builtin_clz(m) == __builtin_clz(i)) DP[m] += B[i]*DP[m^i];
DP[0] = 1;
int Q; cin >> Q;
while (Q--) {
string S; cin >> S;
int m = 0;
for (int i = 0; i < N; ++i) if (S[i] == 'H')
m |= 1<<i;
cout << DP[m]*DP[(1<<N)-1^m] << '\n';
}
}
/*
for i in (seq 18)
./1<p/{$i}.in>out
diff out p/{$i}.out
echo $i OK
end
*/
|
