闲话
场上看 T3 30min 后
得到了一个 Trie 分裂合并 + 手写平衡树优化珂朵莉树 的巨大恶心做法
感性证了一波复杂度是 \(O(n\log n)\) 的
然后
“如果正解真和这个sb做法沾边我就不改了“
“有人曾说过，noi系列的题都是简洁明丽的题目，码农题算了算了”
然后突然想到 [Ynoi2013] Ynoi 似乎有些眼熟
浅看了一眼题解
我超 我这做法没啥问题
然后摆了
最后 APJifengc 通过高超的 bdfs 技巧发现了题解
就是这个做法
然后白兰了（
虽然最后改了这题
今日推歌是lili. - 有機酸
很空灵的感觉呢！
2:07 开始的那段独奏真是 绝了
急了 为啥洛谷不上 ABC284 的题（
杂题
给定一张 \(n\) 个点 \(m\) 条边的网络，源点为 \(1\)，汇点为 \(n\)。对于每条边，有容量 \(c\)，当前流量 \(f\)。但这个图是错误的，可能存在 \(c < f\)，或者流量不守恒的情况。你每次操作可以将某条边的 \(c\) 或 \(f\) 加 \(1\) 或减 \(1\)。请你用最少的操作次数将图变成一个正确的网络。
\(n,m \le 100\)，\(c,f \le 10^6\)，\(1\) 没有入边，\(n\) 没有出边。
……补题计划？
首先我们可以讨论一条边。我们需要让每条边自己流满 \(f\)，然后考虑如下的策略来退流：
- \(f \le c\)
- 减小 \(f\)，等价于 \(v\to u\) 增流，代价为 \(1\)。
- 增加 \(f\) 但是不到 \(c\)，等价于 \(u\to v\) 增流，代价为 \(1\)。
- 增加 \(f\) 至超过 \(c\)，等价于 \(u\to v\) 增流，代价为 \(2\)。
- \(f > c\) 我们至少要花费 \(f - c\) 的费用。
- 减小 \(f\) 但大于 \(c\)，等价于 \(v\to u\) 增流，代价为 \(0\)，因为已经在上面花费了。
- 增加 \(f\) 且小于 \(c\)，等价于 \(v\to u\) 增流，代价为 \(1\)。
- 增加 \(f\)，等价于 \(u\to v\) 增流，代价为 \(2\)。
我们想让原边流满，就考虑先连原边，流量为 \(f\)，花费为 \(0\)，然后建超级源汇点去平衡每个点不平衡的流量。有了超级源汇点之后连 \(n\to 1\) 的无限流量 \(0\) 费边转化为正常最小费用最大流求解即可。
总时间复杂度为 \(O(\text{Dinic}(n, n + m))\)。
你打算在纸上印一串长度为 \(n\) 的字母。为了完成这项工作，你决定刻一个印章。印章每使用一次，就会将印章上的所有字母印到纸上。
同一个位置的相同字符可以印多次。例如：用
aba这个印章可以完成印制ababa的工作（中间的a被印了两次）。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。例如：用aba这个印章不可以完成印制abcba的工作。最小化印章大小。\(n \le 10^7\)。
考虑 \(DP\)。我们设 \(f(i)\) 为印前 \(i\) 个字母的最小印章长度。容易发现 \(f(i)\) 可以等于 \(i\)。
然后我们关注还有什么情况是可以转移过来的。做 kmp，得到 \(nxt_i\)。
容易发现对于一个决策点，只需要决策 \(i\) 和 \(f(nxt_i)\) 即可，具体可以通过归纳法证明。
然后我们只需要判定什么时候可以选择 \(f(nxt_i)\)。我们只需要在 \([i - nxt_i, i]\) 中选出一个 \(j\) 使得 \(f(j) = f(nxt_i)\)。也就是我们可以从 \(nxt_j\) 处一直粘过来并且可以衔接。
开桶保存最大的 \(j\) 即可。总时间复杂度 \(O(n)\)。
浅析 Bostan-Mori 算法
求解线性递推可以直接对求解的数列构造生成函数，然后用一个分式来刻画数列。因此我们可以通过快速求有理分式第 \(n\) 项系数求解线性递推。
我们假设我们需要求解的有理分式形如 \(\dfrac{P(x)}{Q(x)}\)。我们可以在上下分别乘一个 \(Q(-x)\)。这就得到
\[\frac{P(x)Q(-x)}{Q(x)Q(-x)} \]设 \(V(x) = Q(x)Q(-x)\)。容易发现 \(V(x) = V(-x)\)，也就是 \(V(x)\) 只有偶次项。记 \(V(x)\) 为 \(U(x^2)\)。
我们可以将 \(P(x)Q(-x)\) 按指数的奇偶性分为两组，指数为偶数的记为 \(E(x^2)\)，为奇数的记为 \(xO(x^2)\)。这样拆分如上的式子得到
这样朴素实现的话递归即可。由于我们构造的多项式是比较对称的，具有良好的性质，因此可以通过一些观察减少常数。
标签：nxt,闲话,可以,等价,印章,23.1,增流,我们 From： https://www.cnblogs.com/joke3579/p/chitchat230109.html