NOI2021 题解
问题：
- 「对题意换一种理解角度」真的很实用，但 xml 这个二货老是忘记。
- 拿到题目就脑子一热，该冲暴力的刚正解，正解好想的就像魔怔了一样刚暴力（好像是在回避什么？
- 调题不开 -Wall
- 命名混乱
这次的 D1T1 和 D1T2 都应当 AC。
D1T1 轻重边
看作链上染色，一条边是重边的充要条件是两端颜色相同。
然后就做完了woc！！！树剖 + SGT 维护合法边个数，SGT 只要记录左右端点颜色即可合并，很套路的做法。
五味杂陈，所谓的冲高端就是这种套路大杂烩也冲不出来吗？？？
不过算是锻炼树剖了。
D1T2 路径交点
好像是大 sb 题…… 然而我连矩阵行列式都没想到…… 甚至没想到容斥系数之类的…… 偶数 - 奇数，显然是有个 $(-1)^k$ 的容斥系数嘛……
逆序对数，奇偶，想到矩阵行列式。
又是和路径有关的。（实际上这就个 LGV 板题）
$k = 2$ 和 A 性质，答案显然为邻接矩阵行列式的值，等于邻接矩阵相乘后的矩阵行列式的值。
推广到一般，乘得一个 $n_1 * n_k$ 的矩阵 而 $n_1 = n_k$，题目已经写得很裸了
很打脸了，就在同步赛的前几天还订正了 XJ 一道 LGV 套容斥题，自诩为 LGV 爱好者
D1T3 庆典
先缩点。考虑题目里那个性质，它告诉我们缩点后，假设三个块 $x$、$y$、$z$ 之间的关系是 $x$ -> $y$, $y$ -> $z$, $x$ -> $z$
不妨忽略 $x$ -> $z$，这并不影响连通性/可达性
剩下一棵外向树。
$K$ 很小，考虑从起点开始 bfs，扩展到子树里连出去的新边的端点（可以直接枚举新边是哪条），并用树剖记录路径。设扩展次数的阈值为 $4$ 左右能过。
细节：去除多余 DAG 上边的步骤：每个点在最终外向树上的父亲是它 DAG 上所有父亲中拓扑序最大的那个。
卡常：无，跑挺快的。
D2T1 量子通信
脑筋急转弯一样的题。
注意到 $a1$、$a2$ 随机，也就是说串随机生成。
将 $256$ 划为 $16$ 段，某个模式串合法的必要条件是至少一段完全相同，而这就够了因为完全相同的概率是 $\frac{1}{2^{16}}$，这样一次询问需要 check 的模式串个数期望为 $\frac{n}{65536}$ ≈ $7$。
卡常，要用链表代替 vector。
D2T2 密码箱
xml 是 sb……
互质条件在演你，因为假设当前分数为 $y/z$（$gcd(y, z) = 1$），$x + y/z = (xz + y)/z$, $gcd(xz + y, z) = gcd(y, z) = 1$
所以分子分母是独立的！可以矩阵维护。那么你会矩乘那 $15$ 分了。【苦痛】
我们默认矩乘是在序列上从右往左的。
W：令 $a_n = a_n + 1$, 左乘矩阵即可。E 也是左乘矩阵即可。
平衡树维护 flip 和 reverse 操作。flip：维护区间 flip 的结果矩阵。