朵朵绽放的烟火，
化作无尽的繁星闪烁。
春风再度吹过寒冷的铁索，
带走了谁的思绪，
又正在向谁诉说。童年的小翼龙 2024年2月25日
记录了一些以前没见过的题。
CF1567F One-Four Overload
记一个被标记的单元格的度数为其四周的没有被标记的单元格的个数，则：
- 若存在奇度格子，无解。
- 对于度数为 \(2\) 的格子，一定是一个 \(1\) 一个 \(4\)，可以黑白染色，可以证明这样一定有解（installb 的博客）。
- 对于度数为 \(4\) 的格子，若有一种染色方案从逆时针方向为 \(1,1,4,4\)，则一定可以转换为一种逆时针方向为 \(1,4,1,4\) 的方案，于是就和度数为 \(2\) 的证明相同了。
综上，若有解，黑白染色然后输出方案即可。
2024.2.25 至 2024.3.2
UOJ461. 新年的Dog划分
如果我们能够得到这张图的一个 DFS 树，我们就可以黑白染色，然后在删掉所有左右部点之间的非树边的情况下，每次尝试删掉一条树边，如果在删掉某一条树边之后图仍然联通，说明这不是一个二分图。
我们怎么 DFS 呢？考虑在 DFS 的过程中维护一下对于当前已经 DFS
出的树，一定不在树上的边，先将它们全部删去，这可以用一个
set 去维护。对于一个点 \(u\)，我们先找出所有没有被访问过的点（这可以用一个
vis 数组去维护），将它们放在一个 vector
中，记为 \(t\)，然后找到最小的一个
\(i\)，使得删去 \(t_1\dots t_{i-1}\) 和 \(u\) 之间的边之后图仍然联通，但是删去 \(t_1\dots t_i\) 和 \(u\) 之间的边之后图不联通。这保证了 \(u\) 和 \(t_i\) 之间一定有一条边，于是我们将 \(t_i\) 作为 \(u\) 的儿子进行 DFS。在回溯到 \(u\) 之后仍然继续上述过程，直到找不出这样的
\(i\)。这时，我们就可以对于 \(\forall i\)，将此时的 \(t_i\) 与 \(u\) 之间的边标记为不在当前 DFS
树上，然后回溯。
这样，我们就可以在 \(n \log n + O(n)\) 的时间复杂度内找出原图的一棵 DFS 树，可以通过本题。
P3679 [CERC2016] 二分毯 Bipartite Blanket
Ex Hall 定理：
- 若存在一个匹配 \(X\) ，左部点点集为 \(A\)，同时存在一个匹配 \(Y\)，右部点点集为 \(B\)。
- 则一定存在一个匹配 \(Z\)，使得其左右部点点集 \(U,V\) 满足 \(A \subset U, B \subset V\)。
于是我们可以对于左右部点的每个集合去使用 Hall 定理求解，最后双指针统计答案。
使用 Hall 定理求解的时候，可以对于一个集合 \(S\)，设 \(f(S)=[|D(S)|<|S|]\)，其中 \(D(S)\) 表示其通过边连接的对面部点的集合，于是对 \(f\) 做一个高维前缀和就可以求得答案。
QOJ6508. This is not an Abnormal Team!
题意：将一张二分图划分成若干条不相交，且长度小于等于三的链。最小化孤立点的个数。在此基础上，最小化长度为 \(3\) 的链的个数。
先考虑第一问，使用网络流。记网络流的源点、汇点为 \(S,T\)，将网络流求最大匹配的连边改为 从 \(S\) 往外连边容量为 \(2\)，往 \(T\) 连边容量为 \(2\) 。注意到这样最后方案可能会是一些环或链，但是任何环或者链都可以切成若干个长度小于等于 \(3\) 的链。
再考虑第二问，在第一问的基础上，我们可以给边一个费用。先将容量为 \(2\) 的边分开成 \(2\) 条，然后将每一个点（左部或右部点）和 \(S、T\) 之间的连边中的第一条边费用设为 \(-\infty\)，第二条边费用设为 \(1\)，然后跑 最小费用可行流。这样，会优先使得每一个点都不是孤立点，可行流则会使得长度为 \(3\) 的链个数最小。
CF1383F Special Edges
最大流=最小割。
由于 \(k\) 很小，我们可以暴力枚举哪些特殊边被割掉，将被割掉的边容量设为 \(0\)，没被割掉的容量设为 \(\infty\)，总共有 \(2^k\) 种情况。询问的时候通过枚举这 \(2^k\) 种情况，用上述求出的最小割加上割掉的边现在的边权，求出真正的最小割即可。
于是问题转化为了每次将 \(1\) 条边的边权从 \(0\) 调整为 \(\infty\)，求最大流。最开始先令所有边容量为 \(0\)，跑一遍最大流。对于每种情况，可以先从 \(S-\operatorname{logbit}(S)\) 转移过来，然后再在残量网络上跑最大流，由于容量小于等于 \(25\)，可以令 \(\inf=25\)，然后用 EK来求取最小割，时间复杂度 \(O(mw2^k+q2^k)\)，其中最大边权 \(w\le 25\)。\(\Huge\color{red}{卡}\color{yellow}{卡}\color{blue}{就}\color{green}{过}\color{pink}{了}\)
P3354 [IOI2005] Riv 河流
反着 DP 的题，比较少见。
考虑设 \(f_{i,j,k}\) 代表考虑 \(i\) 的子树，离 \(i\) 最近有伐木场的祖先离 \(i\) 的距离为 \(j\)，当前还能最多设置 \(k\) 个伐木场的最小代价，转移显然。
时间复杂度 \(O(n^2k^2)\)。
P7295 [USACO21JAN] Paint by Letters P
将方格看成点，颜色相同的点之间连边，则所有的点和边构成了一张平面图，我们每次要求的是一个子图的联通块个数。由平面图欧拉公式可知：\(|V|-|E|+R=C+1\)，其中 \(V\) 为点集，\(E\) 为边集，\(R\) 是面数（包含内部面和外部面），\(C\) 是联通块个数。我们询问的子图是一个矩形状物，所以用二维前缀和求出边数，点数可以直接算出，关键是面数不好算。
容易发现我们只需要计算内部面的个数 \(R'\)，则答案为 \(|V|-|E|+R'\)。我们按下图对空格编号（星星是空格），则我们可以先用 dfs 或 bfs 求出所有的面，现在只需要判断哪些面完全在我们询问的子图中。显然，如果一个面只有一部分在我们询问的子图中，它一定会和外部面融为一体，不参与 \(R'\) 的计算。
我们可以对每一个面任意选出一个代表空格，我们可以先假装只要包含代表空格，这个面就全部在我们询问的子图中，这可以用二维前缀和解决。在询问的时候，我们通过遍历我们询问的子图周围的 \(O(n)\) 个空格，来判断哪些面满足：其代表空格在询问的面之内，但是其有一部分不在询问的子图内。因为我们遍历的就是子图周围（不在子图内）的空格，所以如果这些面的代表空格在子图内，就可以给 \(R'\) 减去 \(1\)。注意若干个空格可能同属于一个面，对于这样的情况，我们只需要减去一次。
时间复杂度 \(O(nm+q(n+m))\)。
P5807 【模板】BEST 定理 | Which Dreamed It
BEST 定理：
对于一张有向欧拉图 \(G=\{V,E\}\)，其欧拉回路个数为
\[
T_{root}(G)\times\prod_{i\in V}(d_i-1)!
\]
其中 \(T_{root}(G)\) 代表 \(G\)
的任意一点为根的根向生成树个数，可以用矩阵树定理求出；\(d_i\) 表示 \(i\) 的出度。
UOJ226. 【UR #15】奥林匹克环城马拉松
基环树欧拉回路计数。
BEST 定理给出了有向图欧拉回路计数的方式，于是我们可以先将边定向后套用 BEST 定理。
定向：
对于树的部分，每一条边的方向都是确定的，若这条边有 \(t_i\) 条，则有解当且仅当 \(2|t_i\)，且这些边一半向下，一半向上，于是我们定向后给答案乘上一个 \(\displaystyle{t_i\choose\frac{t_i}{2}}\)。
对于环的部分，我们可以枚举绕着环逆时针或顺时针走了 \(k\) 圈，则由欧拉图所有点入度等于出度，我们就可以算出所有点的度数。记一条边有 \(t_i\) 条，其中 \(s_i\) 条逆时针，则我们定向后给答案乘上一个 \(\displaystyle{t_i\choose s_i}\)。
计算根向生成树个数：
我们可以设根是环上的某一个点，则：
对于树的部分，其对生成树个数的贡献是 \(\displaystyle{\prod_{i}\frac{t_i}{2}}\)。
对于环的部分，其对生成树个数的贡献可以先对顺时针和逆时针的边的个数做一个前缀乘，然后枚举断掉一条边来算出。
计算答案：
对于每一种逆/顺时针转了 \(k\)
圈的方案，我们记其边定向方案个数和生成树个数的乘积为 \(calc(k)\)，此时每个点 \(i\) 的度数为 \(d_i\)，则答案为
\[
\sum_{k}calc(k)\prod_{i}(d_i-1)!
\]
时间复杂度 \(O(n\max{t_i})\)。
#include <bits/stdc++.h>
using namespace std;
namespace Slongod{
const int N = 2e3+7 , M = 1e7+7 , mod = 998244353;
int n , m , ans , d[N] , cirank[N] , c[N] , cb[N] , rb[N] , pr[N] , sf[N] , pre[M] , inv[M]; bool vis[N];
vector <int> sta , vt , g[N]; vector <pair<pair<int,int>,int>> edge;
inline int qkpow(int x , int y){int s;for(s=1;y;y/=2,x=1ll*x*x%mod){if(y&1){s=1ll*s*x%mod;}}return s;}
inline void init()
{
pre[0] = 1; for (int i = 1; i < M; i++){pre[i] = 1ll * pre[i-1] * i % mod;}
inv[M-1] = qkpow(pre[M-1] , mod - 2); for (int i = M - 2; i >= 0; i--){inv[i] = 1ll * inv[i+1] * (i+1) % mod;}
}
inline int C(int nn , int mm){return nn >= mm ? 1ll * pre[nn] * inv[mm] % mod * inv[nn-mm] % mod : 0;}
bool dfs(int u , int fa)
{
vis[u] = 1; sta.push_back(u);
for (auto v : g[u]) {
if (v != fa) {
if (!vis[v]) {
if (dfs(v , u)) {
return true;
}
} else {
sta.push_back(0);
do {
sta.pop_back();
vt.push_back(sta.back());
} while(sta.back() != v);
return true;
}
}
} sta.pop_back(); return false;
}
void main()
{
cin >> n >> m; init();
for (int i = 1 , x , y , t; i <= m; i++) {
cin >> x >> y >> t;
g[x].push_back(y); d[x] += t;
g[y].push_back(x); d[y] += t;
edge.push_back({{x , y} , t});
}
for (int i = 1; i <= n; i++){if (d[i] & 1){cout << 0 << '\n'; return;}}
if (!dfs(1 , 1)) { //没有环
ans = 1;
for (int i = 0; i < m; i++) {
ans = 1ll * ans * C(edge[i].second , edge[i].second / 2) % mod;
ans = 1ll * ans * edge[i].second / 2 % mod;
}
for (int i = 1; i <= n; i++) {
ans = 1ll * ans * pre[d[i] / 2 - 1] % mod;
}
} else {
ans = 0; sta = vt;
int cirsize = sta.size() , minn = 0x3f3f3f3f;
memset(cirank , -1 , sizeof(cirank));
for (int i = 0; i < cirsize; i++){cirank[sta[i]] = i;}
for (int i = 0; i < m; i++) {
if (~cirank[edge[i].first.first] and ~cirank[edge[i].first.second]) {
c[(cirank[edge[i].first.first] + 1) % cirsize == cirank[edge[i].first.second] ? cirank[edge[i].first.first] : cirank[edge[i].first.second]] = edge[i].second;
minn = min(minn , edge[i].second);
}
}
for (int k = -minn , ok = 1 , sum = 0 , tans = 1; k <= minn; k++ , ok = 1 , sum = 0 , tans = 1) {
memset(d , 0 , sizeof(d));
for (int i = 0; i < cirsize; i++) {
if ((c[i] + k) & 1){ok = 0; break;}
cb[i] = (c[i] + k) / 2;
rb[i] = (c[i] - k) / 2;
tans = 1ll * tans * C(c[i] , cb[i]) % mod;
d[sta[i]] += cb[i]; d[sta[(i+1)%cirsize]] += rb[i];
} if (!ok){continue;}
for (int i = 0; i < m; i++) {
if (!~cirank[edge[i].first.first] or !~cirank[edge[i].first.second]) {
d[edge[i].first.first] += edge[i].second / 2;
d[edge[i].first.second] += edge[i].second / 2;
tans = 1ll * tans * C(edge[i].second , edge[i].second / 2) % mod;
tans = 1ll * tans * edge[i].second / 2 % mod;
}
}
for (int i = 1; i <= n; i++) {
tans = 1ll * tans * pre[d[i] - 1] % mod;
}
pr[0] = rb[0]; for (int i = 1; i < cirsize; i++){pr[i] = 1ll * pr[i-1] * rb[i] % mod;}
sf[cirsize-1] = cb[cirsize-1]; for (int i = cirsize-2; i >= 0; i--){sf[i] = 1ll * sf[i+1] * cb[i] % mod;}
for (int i = 0 , t = 1; i < cirsize; i++ , t = 1) {
if (i){t = 1ll * t * pr[i-1] % mod;}
if (i != cirsize-1){t = 1ll * t * sf[i+1] % mod;}
sum = (sum + t) % mod;
} ans = (ans + 1ll * tans * sum) % mod;
}
} cout << ans << '\n';
}
}int main()
{
#ifndef ONLINE_JUDGE
freopen("ex.in" , "r" , stdin);
#endif
ios :: sync_with_stdio(0);
cin.tie(0) , cout.tie(0);
return Slongod :: main(),0;
}P3350 [ZJOI2016] 旅行者
下文中记 \(n\) 为面积。
考虑离线所有询问后分治矩形。对于当前矩形，每次切两维中较长的那一维，对于中线上的 \(O(\sqrt{n})\) 个点跑最短路，然后对于每一个询问用这 \(\sqrt{n}\) 个点拼出路径。若询问的两点在中线的两侧，则这次的答案对于当前矩形来说一定是最优的，不再继续分治。若询问的两点在中线的一侧，则可能不跨过中线更优，继续往小矩形分治。
使用堆优化的 dijkstra 最短路算法，时间复杂度 \(T(n)=2T(n/2)+n\sqrt{n}\log n=O(n\sqrt{n}\log n)\)。
P9040 [PA2021] Desant 2
考虑 DP，设 \(f_i\) 表示考虑前 \(i\) 个人的最大收益，则
\[
f_i=\max\{f_{i-1},f_{i-k}+\sum_{j=i-k+1}^{i}a_j\}
\]
由于 \(k\) 固定，我们如果将 \(i\) 向 \(i+1\) 和 \(i+k\) 连边，则整张图构成了一个 \(\frac{n}{k}\) 行 \(k\)
列的网格图状物。非最后一行的最后一列有着向下一行第一列的连边。
于是我们就可以像上一道题（旅行者）一样，对网格图分治。由于是有向边，直接 DP 会比跑最短路快得多。注意最后一列有向第一列的连边，于是我们在竖着劈第一刀之前需要先算出这些边可能影响的答案。具体地，直接以最后一列或第一列为中线跑一遍 DP，然后对答案贡献即可。
时间复杂度 \(O(n\sqrt{n})\)。
CF850F Rainbow Balls
停时定理：对于一个状态 \(S\)，如果能设计一个函数，使得对于 \(S\) 的所有后继状态 \(S'\)，\(E[F(S')-F(S)]=-1\)。对于停止的状态 \(R\)，则停止的期望步数等于 \(F(T)-F(R)\)，其中 \(T\) 是起始状态。
对于本题，我们可以设 \(\displaystyle
F(S)=\sum_if(a_i)\)，则有
\[
\sum_{i}f(a_i)-1=\sum_{i}\frac{a_i(a_i-1)+(m-a_i)(m-a_i-1)}{m(m-1)}f(a_i)+\frac{a_i(m-a_i)}{m(m-1)}(f(a_i+1)+f(a_i-1))
\]
移项并化简可得
\[
-1=\sum_{i}\frac{(a_i^2-a_im)f(a_i)-(a_i^2-a_im)f(a_i+1)+(a_i^2-ma_i)f(a_i)-(a_i^2-ma_i)f(a_i-1)}{m(m-1)}
\]
令 \(g(x)=f(x)-f(x+1)\)，则
\[
-1=\sum_{i}\frac{a_i(a_i-m)}{m(m-1)}(g(a_i)-g(a_i-1))\\
\]
令 \(\displaystyle
\frac{a_i(a_i-m)}{m(m-1)}(g(a_i)-g(a_i-1))=-\frac{a_i}{m}\)，则
\[
g(a_i)-g(a_i-1)=\frac{1-m}{a_i-m}
\]
因此
\[
g(x)=g(x-1)+\frac{1-m}{x-m}\\
f(x)=f(x-1)-g(x-1)\\
ans=f(m)-\sum_if(a_i)
\]
令 \(f(0)=g(0)=0\)，其他可以递推计算。对于 \(f(m)\) 我们有：
\[
\begin{aligned}
f(m)&=-\sum_{i=0}^{m-1}\sum_{j=1}^{i}\frac{1-m}{j-m}\\
&=-\sum_{j=1}^{m-1}(m-1-j+1)\frac{1-m}{j-m}\\
&=\sum_{j=1}^{m-1}1-m\\
&=(m-1)(1-m)
\end{aligned}
\]
时间复杂度 \(O(n+\max
a_i)\)，直接快速幂会多只 \(\log\)。
CF1349D Slime and Biscuits
和上道题一样。
CF1025G Company Acquisitions
有些时候，加强式子的限制反而有利于推出答案。
本题和前两道题大同小异，设 \(a_i\) 表示追随 \(i\) 的节点数，\(\displaystyle F(S)=\sum_{i}f(a_i)\)。
假设当前有 \(m\) 个已被选中的点，令
\(f(0)=0\)，我们可以得出：
\[
\begin{aligned}
\frac{1}{m\choose2}\sum_{x=1}^{m}\sum_{y=x+1}^{m}f(x)+f(y)-\frac{1}{2}(f(x+1)+(y-1)f(0))-\frac{1}{2}(f(y+1)+(x-1)f(0))
&=-1\\
\sum_{x=1}^{m}\sum_{y=x+1}^{m}f(x)-\frac{f(x+1)}{2}+f(y)-\frac{f(y+1)}{2}
&=-{m\choose2}\\
\end{aligned}
\]
现在式子中有 \(m\)，不好处理。我们可以稍微加强一下限制，令
\[
\begin{aligned}
\forall
x,y\enspace,f(x)-\frac{f(x+1)}{2}+f(y)-\frac{f(y+1)}{2}&=-1\\
\end{aligned}
\]
显然这个满足这个式子也会满足前面的式子。对于这个式子，我们只需要令 \(f(x)\) 满足以下条件：
\[
\begin{aligned}
f(x)-\frac{f(x+1)}{2}&=\frac{1}{2}\\
f(x+1)&=2f(x)-1
\end{aligned}
\]
于是，我们就可以在 \(O(n)\)
的时间复杂度内递推出所有的 \(f(i)\)，答案即为 \(\displaystyle f(n-1)-\sum_{i\in
S}c_i\)，其中 \(c_i\)
代表最开始追随 \(i\) 的人数，\(S\) 代表最开始被选定的点的集合。
CF1479E School Clubs
同上。
P3188 [HNOI2007] 梦幻岛宝珠
题意：01 背包，但是容量是 \(2^{30}\)，保证所有物品的体积表示为 \(a\times 2^k\) 后，\(a\le 10\)。
我们先将所有物体按体积中的 \(k\) 分类，每一种分类中可以求出本类中最优方案，由 \(n\le 100,a\le 10\) 可知，每一类中的总容量不会大于 \(1000\)。我们记种类 \(i\) 中耗费 \(j\times 2^i\) 的容量能获得的最大价值为 \(f_{i,j}\)，则对于每一类物品，\(f\) 可以在 \(O(|S_i|^2V)\) 的时间复杂度内用普通 01 背包求出，其中 \(S_i\) 代表本类物品的集合，\(V\) 代表 \(a\) 的最大值。
考虑从小到大枚举物品的种类，当枚举到第 \(i\) 类的时候，我们最多只需要 \(1000\times 2^i\)
的容量，所以背包的总容量可以和这个数字取一个 \(\min\)。并且对于小于 \(i\)
的二进制位，它们是否有值对于当前的问题是没有意义的，因为我们已经考虑完了小于
\(i\)
的所有位，当前物品所需要的最小容量也一定是大于等于 \(2^i\) 的。因此，我们可以设 \(g_{i,j}\) 表示考虑前 \(i\) 类物品，用小于等于 \(j\times2^i\)
的容量所能获取的最大价值，转移如下：
\[
g_{i,j}=\max_{k=0}^{\min(|S_i|V,j)}f_{i,k}+g_{i-1,(j-k)\times2+W_{i-1}}
\]
其中 \(W_i\) 代表 \(W\) 的二进制表示第 \(i\) 位上的数字。最终答案即为 \(g_{\log_2{W},1}\)。
P3226 [HNOI2012] 集合选数
对于两个数，若他们质因数分解并去掉所有的 \(2,3\) 因子后不同，则它们不可能互相影响，我们将去掉所有 \(2,3\) 质因数后相等的数字称作同一类数，则我们只需要对每类数求出方案后乘起来即可。
将一类数列作一个网格图，每一行的的数满足右边的数是左边数的 \(3\) 倍，每一列的数满足是左边数的 \(2\) 倍，就可以状压 DP 了。设 \(f_{i,j}\) 为考虑了前 \(i\) 行，当前行选没选的状态为 \(j\) 的方案数，直接枚举下一行的方案转移就行。
时间复杂度上界 \(O(\log_2n\times \log_3^2n)\)，在预处理出每一行所有的可能状态（不考虑上下两行）后，真正的计算量远远小于这个上界。
P6246 [IOI2000] 邮局
转化：钦定每一个邮局管辖一定区域，这个区域都要来这个邮局。则转化后的问题的最优解一定是原问题的最优解。
于是变成了将序列划分为若干段，每一段 \([l,r]\) 有代价 \(w(l,r)\)，要求总代价和最小。写出 \(w\) 的递推式：
\[
W_{l,r}=W_{l,r-1}+X_r-X_{\lfloor\frac{l+r}{2}\rfloor}
\]
满足四边形不等式，于是用单调队列优化决策单调性后+WQS二分之后可以做到
\(O(n\log n\log V)\)。
CF1217F Forced Online Queries Problem
如在线问题。
根据强制在线的方式，每一次只可能影响两条不同的边，我们可以先将每一条边在可能会修改它的时间打一个时间戳，就可以对应的所有时间区间搞出来。在线段树分治到一次询问的时候，我们遍历这个答案影响的所有询问，看到底某条边在下个时间区间存在还是不存在，然后继续线段树分治即可。