牢游看见我正在做插头 dp，于是给我了一个 Claris 的连通性 dp 的 pdf。

好了，现在又有可以软性颓废的事可干了。

好多题目在其他平台都找不到了，这时候我们 becoder 的优越性就体现出来了！（这就是到处搬题的好处）所以大部分题目链接都会放 becoder 的链接。

什么？你不知道 becoder 或者没有 becoder 账号？亲爱的快快点我去进行注册吧！

（注意到这是一个推广链接，燕国的地图还是太短了。但是这个 72 小时刷新一次是不是也在变相催更我自己啊。）

后面考虑补一个插头 dp 的学习笔记？

插头 dp 学习笔记

咕咕咕

插头 dp 做题笔记

Becoder# 10030. Ants

如果做过模板题了的话这道题就很轻松了。

从图论的角度考虑，最后每个格子仍然有麻衣蚂蚁的话那么每个格子都会恰好有一个入度，所以会形成若干个有向回路。

回路覆盖计数是经典的插头 dp，而且这道题还没要求是一条回路！那就更简单了，定义三种插头：\(0\) 表示无插头，\(1\) 表示出度插头，\(2\) 表示入度插头：

分以下几种情况讨论：

1. 右插头和下插头都是空插头：此时直接新建两个插头，一个入度插头和一个出度插头，因为每个格子都必须被回路覆盖到。
2. 有一个空插头，另一个是非空插头：可以继续按照原来的方向延续这个插头，或是使其转向（右插头变下插头，下插头变右插头），注意插头的类型不能改变。
3. 两个都是非空插头，直接合并，注意要判断两个插头是否是一个入度插头一个出度插头，如果不是的话需要忽略掉。

roll 的时候要把行末还有右插头的状态舍弃掉。

代码还是轻松的：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int mod = 299987;
int n, last = 1, now, bit, lx, dx, cnt[2], head[mod], nxt[200005], q[2][200005];
ll v, val[2][200005];
void push(int bit, ll v) {
	static int r, pos;
	r = bit % mod, pos = head[r];
	while(pos) {
		if(q[now][pos] == bit) {
			val[now][pos] += v;
			return;
		}
		pos = nxt[pos];
	}
	nxt[++cnt[now]] = head[r];
	head[r] = cnt[now];
	tie(q[now][cnt[now]], val[now][cnt[now]]) = tie(bit, v);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	push(0, 1);
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= cnt[now]; ++j) {
			if(q[now][j] >> (n << 1)) val[now][j] = 0;
			q[now][j] <<= 2;
		}
		for(int j = 1; j <= n; ++j) {
			swap(last, now);
			fill(head, head + mod, 0);
			cnt[now] = 0;
			for(int k = 1; k <= cnt[last]; ++k) {
				tie(bit, v) = tie(q[last][k], val[last][k]);
				if(!v) continue;
				lx = (bit >> ((j - 1) << 1)) & 3, dx = (bit >> (j << 1)) & 3;
				if(!lx && !dx) {
					push(bit ^ (1 << ((j - 1) << 1)) ^ (2 << (j << 1)), v);
					push(bit ^ (2 << ((j - 1) << 1)) ^ (1 << (j << 1)), v);
				}
				else if(lx && !dx) {
					push(bit, v);
					push(bit ^ (lx << ((j - 1) << 1)) ^ (lx << (j << 1)), v);
				}
				else if(!lx && dx) {
					push(bit, v);
					push(bit ^ (dx << ((j - 1) << 1)) ^ (dx << (j << 1)), v);
				}
				else if((lx ^ dx) == 3) {
					push(bit ^ (lx << ((j - 1) << 1)) ^ (dx << (j << 1)), v);
				}
			}
		}
	}
	for(int i = 1; i <= cnt[now]; ++i) {
		if(!q[now][i]) {
			cout << val[now][i];
			return 0;
		}
	}
	cout << "0";
	return 0;
}