构造一个 n3 个点的无向图 G，方法如下：
- 给定 3 张 n 个点的无向图 G1,G2,G3。
- 构造 n3 个点，标号是一个三元组 ⟨i,j,k⟩。
- 对于 G1 中的边 ⟨u,v⟩，连边 ⟨u,j,k⟩ 和 ⟨v,j,k⟩。
- 对于 G2 中的边 ⟨u,v⟩，连边 ⟨i,u,k⟩ 和 ⟨i,v,k⟩。
- 对于 G3 中的边 ⟨u,v⟩，连边 ⟨i,j,u⟩ 和 ⟨i,j,v⟩。
- 对于 G 上的一个点 ⟨i,j,k⟩，其点权为 1018(i+j+k)。
现在，要你求出 G 的最大独立集大小膜 998244353 以后的值。
2≤n≤105,1≤m1,m2,m3≤105
考虑到是点权是一个大数的幂次，那肯定是选的数越大越好。
考虑如果你知道了图 G 之后你会怎么做。
首先 ⟨n,n,n⟩ 这个点必须得选，然后其跟她连边的点就不能选了。
然后如果一个点已经确定了旁边已经比她大的点都不选了，那么她才会选。
那会不会有两个相邻的点点权相等呢？显然不会。因为相邻的点必须有两个权值相等，那么另外一个肯定相等，这是不合法的。
然后我们就考虑这个过程，就是我们考虑如何判断一个点选不选，那就要看与之相邻的比她大的点选不选，就是如果那些点都是不合法的，那么这个点合法，否则不合法。
我们发现这跟博弈问题很像，就是有 3 颗棋子，每个人每次可以把一个棋子移动到一个比她大的格子里，不能走的就输了。而先手必输态的点就是合法的。
于是我们只要计算每个点的 sg 值即可。
考虑到每张图 sg 值只会有 O(n) 个，我们只要计算出之后暴力合并即可，于是合并复杂度是 O(n) 的。
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
| namespace dfcmd {
typedef long long LL;
const int maxn = 100005;
const int mod = 998244353;
const int di = 1000000000000000000LL % mod;
int bin[maxn];
inline void add(int& x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
int n;
struct myhnb {
int m;
int sg[maxn];
int ss[maxn];
struct Edge {
int to, nxt;
} e[maxn];
int first[maxn];
int cnt = 0;
inline void add_edge(int u, int v) {
if (u > v) {
swap(u, v);
}
e[++cnt].nxt = first[u];
first[u] = cnt;
e[cnt].to = v;
}
int vis[maxn];
myhnb() {
memset(first, 0, sizeof(first));
memset(ss, 0, sizeof(ss));
memset(vis, 0, sizeof(vis));
}
inline void Dfs() {
for (int now = n; now; --now) {
vis[now] = true;
set<int> sgg;
sgg.clear();
for (int i = first[now]; i; i = e[i].nxt) {
sgg.insert(sg[e[i].to]);
}
sg[now] = 0;
while (sgg.count(sg[now])) {
sg[now]++;
}
add(ss[sg[now]], bin[now]);
}
}
inline int& operator [] (int x) {
return ss[x];
}
} d[3];
int main() {
read(n);
bin[0] = 1;
for (int i = 1; i <= n; ++i) {
bin[i] = (LL) bin[i - 1] * di % mod;
}
for (int i = 0; i < 3; ++i) {
read(d[i].m);
for (int j = 1; j <= d[i].m; ++j) {
int u, v;
read(u), read(v);
d[i].add_edge(u, v);
}
d[i].Dfs();
}
int ans = 0;
for (int i = 0; i <= 1000; ++i) {
for (int j = 0; j <= 1000; ++j) {
add(ans, (LL) d[0][i] * d[1][j] % mod * d[2][i ^ j] % mod);
}
}
writeln(ans);
return 0;
}
}
|
