Link. 有附加内容。懒得搬了。

最喜欢的一集。

题目的要求十分简洁，但是贡献的计算非常繁琐诡异，而 $n$ 非常小。基本上可以直接放弃别的想法直奔网络流了。

观察一下贡献的形式，发现 $d_{i, j}$ 的贡献方式是我们熟悉的，可以用最大权闭合子图的模型来描述。所以考虑一下最小割。

除了 $d_{i, j}$ 我们还有一个 $mx^2 + cx$ 的贡献。这两个贡献仍然可以看作最大权闭合子图。具体地，选上 $d_{i, i}$ 后会产生 $ma_i^2$  的代价，如果之前已经产生过了则无所谓。给每种类型建一个点即可。

类似地，$cx$ 可以平摊到每次选 $x$ 的位置上，对 $d_{i, i}$ 对应的 $a_i$ 建立点 $A_i$ 并连边，表示选上 $d_{i, i}$ 则必须选上 $-a_i$。

然后就没了。讲一下最大权闭合子图，考虑这样一个模型：给定一张 $n$ 个点 $m$ 条边的有向图。每个点有代价 $a_i$，可正可负。你可以选上一些点，你的分数是你选的点的 $a$ 之和。但是选点有限制，选上一个点 $x$ 则必须选上 $x$ 能到达的所有点。求最大分数。

这个过程可以看作，选一些正权点，为了得到它们的权值不得不割舍一些负权点的代价。

于是考虑转化一下限制，改写成：选一些正权点，选上一个点后必须选上其所能到达的负权点。

这样做的好处在于，即简化了问题，又保证答案不会改变。感觉非常妙。

然后就是最小割建模。建立源汇点 $S, T$，对于每个正权点 $i$，连 $S\to i$，流量为 $a_i$。对于每个负权点 $i$，连 $i\to T$，流量 $-a_i$。对于正权点 $i$ 和其所能到达的负权点 $j$，连边 $i\to j$，流量 $+\infty$。答案即为正权点权值和减去最小割。

首先建立超源点和超汇点，源点与类型相连，试题与汇点相连，类型与对应试题相连

之后考虑边的容量

每种类型需要的试题有多道，所以源点与类型的边的容量应为该类型所需试题的数量

一道题只有一个，所以试题与汇点的边的容量为1，同理类型与试题的边的容量也为1

求最大流后进行判断，如果最大流等于m，那么寻找容量为0的边对应的类型和试题输出，否则无解

将每天拆成两个点，i点用于接收干净餐巾，i'点用于接收脏餐巾，那么：

·从i向T连流量为Ri，费用为0的边，如果满流则表示当天的餐巾数量足够

·从S向i'连流量为Ri，费用为0的边，表示每天结束时接收到Ri块脏餐巾

·从S向i连流量为∞，费用为p的边，表示每天开始时购买餐巾

·从i'向i+m连流量为∞，费用为f的边，表示送快洗

·从i'向i+n连流量为∞，费用为s的边，表示送慢洗

·从i'向(i+1)'连流量为∞，费用为0的边，表示将脏餐巾留到下一天

之后求最小费用最大流即可

在与牢大战斗两个多月后，“引爆逆天力量，追寻圆环之理的神藏奥秘”系列堂堂打赢复活赛。看来扣1真的有用！

直接做明显没前途，考虑容斥。

注意到位置 $i$ 不合法当且仅当 $a_i<a_{i-1}$ 且 $a_i|a_{i-1}$，即 $a_i$ 为 $a_{i-1}$ 的非自身因数。

考虑有一些非法位置，其他位置随便放，然后钦定非法位置的数为上一位的非自身因数。

然而注意到非法位置的方案数是不好算的，因为可能出现多个非法位置连着的情况，此时各个非法位置是不独立的。

幸运的是，由于 $a_i\le a_{i-1}/2$，每个非法位置连续段的长度不会超过 $\log m$，那我们就可以直接枚举连续段的长度进行DP。

记 $f_i$ 表示 $i$ 作为连续段结尾的容斥贡献，$s_i$ 表示前 $i$ 位的容斥贡献和，那么有

$$f_i=\sum_{j=1}^{\log m} g_j s_{i-j-1} (-1)^j$$

$$s_i=f_i+ s_{i-1}m$$

其中 $g_i$ 表示连续 $i$ 个非法位置，且前一个合法位置随便放的方案数，容易 $O(m\log m)$ 预处理。

显然DP可以矩阵优化，于是做到了 $O(\log^3 m \log n)$ 的复杂度。可能爆标了？

Bonus: 注意到DP是一个线性递推，使用 BM 算法可以做到 $O(\log m \log n \log\log m)$。

显然有一个 $\mathcal O(m\log m)$ 的 LCT 做法：将边按照 $a$ 升序排序，依次加入，动态维护最小生成树，这是 LCT 的经典应用。

那我不会 LCT，又该怎么通过这个题呢？

令人疑惑的是，榜上有大量的神秘复杂度 SPFA 做法，还有评论区中的二分套二分。这显然是错的，事实上不会 LCT 也有对应的常规手段处理。

秉持着 "直接做就好了" 的信念来处理，考虑二分答案转化为判定问题，设二分值为 $mid$。我们要求 $a_{\max} + b_{\max} \le mid$，不好利用判定的优势，于是转化一下，令 $c = mid - b$，那么就是 $a_{\max}\le c_{\min}$。

这个限制可以改写成 $\forall (a, c), a\le c_{\min}\le c$。此时就比较明晰了，使用线段树分治 + 可撤销并查集维护每个 $c_{\min}$ 对应的边，判断是否能形成一棵生成树，如果可行便 check 成功，如果不存在这样的 $c$ 则 check 失败。

时间复杂度 $\mathcal O(m\log^2 m\log n)$。代码也比较好写。

冷静下来想想，这个做法其实是有一些道理的（接下来是自己的碎碎念，并不一定很有意义）。

由 [SDOI2008] 洞穴勘测 我们知道，对于简单的，只含边的加入 / 撤销，判断联通状态，可离线的 LCT 问题，我们可以采用线段树分治 + 可撤销并查集来维护。结合 LCT 维护最小生成树的背景，猜想可以通过一些转化，让条件变成形如 "一条边有少数个存在的范围，判断是否能形成一棵生成树" 这样的问题。

一开始的一些推断告诉我们，直接做不存在好的数学性质，并且只能 LCT 维护，进而想到尝试二分答案转化为相对容易的判定。通过常见手段对限制进行改写，从而使得判定条件中的常数 $mid$ 带来更多作用。结合前面的感觉，得到正确的解法。

COGS 的 G++9.30 评测机还没有好。。。代码就放在 这里 了。由于卡常，代码并不是很可读。

考虑 $k = 1$ 的情况，不妨设 $a$ 降序，此时显然是呈 $\dots, a_4, a_2, a_1, a_3, a_5, \dots$ 状。

然后考虑 $k > 1$，根据数论结论我们知道环长是 $n / \gcd(n, k)$，对于一种环长 $d$，和初始 $k = 1$ 的状态有 $\mathcal O(n / d)$ 处修改，于是记忆化处理，时间复杂度根据调和级数为 $\mathcal O(n\ln n)$。