题目顺序不是做题顺序也不是考试顺序更不是难度顺序，是随机顺序。
为了不影响观看体验决定把代码删去，需要请私信我，QQ或博客园皆可。
题目里的难度评分是个人评分，仅供参考开心就好。
期末考试
难度评分：提高
题意是给定期末考试每门课的出分时间和学生希望的出分时间，如果学生要等就会有不满意度。你可以进行老师的增加和调换操作，但是都会产生不满意度。请最小化不满意度。
先考虑学生的不满意度怎么算：
设(F_i)表示以第(i)天结束学生们不满意度的总和，则(F_i-F_{i-1}=)第(i)天学生们的不满意度总和。
(F_i=Σ_{j=1}^n Max(0,i-b_j)×C)
发现数据范围不大，考虑预处理这个式子，很显然就是个前缀和。
然后再考虑安排老师。分类讨论一下。
若(A geq B)，肯定优先选择(B)操作，即加老师，这样只会使得结束时间都提前。
若(A<B)，肯定优先选择(A)，(A)用完了再用(A)只会使答案变劣的时候用(B)。
考虑用(A)的最多次数：假设第(i)天结束，则所有结束时间比(i)小的都可以贡献老师出来，这就是使用(A)的最多次数。可以用前缀和预处理出来。
由于数据范围不大，前缀和计算又是(O(1))的，直接枚举结束日期计算即可。
复杂度(O(maxn))，(maxn)表示最晚结束日期。
组合数问题
难度评分：普及+
题意是给定(n,k,r,p)，求(Σ_{i=0}^∞ C_{nk}^{ik+r} mod p) 。
由于(m>n)的时候(C_{n}^m=0)，所以实际上(i)只要从(0)~(n)枚举即可。
看起来就很休闲，你会(Lucas)就发现送了(60\%)，预处理一下阶乘和逆元，枚举(i)就可以了。
然后注意到(n leq 10^9,0 leq r leq k leq 50)，于是想到矩阵加速。
组合数的式子是现成的，可以把意义从“(i)个里面选(j)个”改成“(i)个里面选(x\%K==j)个”，直接套用即可。
就是构造上图的矩阵，发现初始值为(0)所以不要管了，直接把中间的做个快速幂，然后就做完了。时间复杂度(O(log(nk)))。
分手是祝愿
难度评分：提高+
题意是有一些给定初始状态的灯，希望他们都灭掉。按下一个开关会影响它及它约数的状态。开始随机按一些开关，如果最后剩下需要的步数(<=k)就用最优解按。求期望次数(×n!)
首先明确怎么算最优解：我们按开关只会影响比它小的，所以我们从大到小按开关，就是枚举每个(i)的倍数放进(vector)，这个复杂度是调和级数也就是(n ln n)的。所以我们统计答案只需要统计(sum_{i=1}^{need} f[i])，(need)表示最优解下需要次数。
然后考虑随机一个按，那我们可能按到当前最优的或其他的。
按到最优解：(frac{i}{n}×1)，这个就表示按到对的按钮的概率为(frac{i}{n})，贡献为(1)次（期望=概率×贡献）。
按到其他按钮：(frac{n-i}{n}×(1+f[i]+f[i+1]))。这个(1)就表示这个按错了的开关还要重新按回来一遍以消除影响，(f[i]+f[i+1])就表示还需要(f[i]+f[i+1])次操作变成(i-1)这个状态。
然后化简一下式子移项把(f[i])推出来，答案再乘上(n!)即可。边界为(f[n]=1)。注意(f[1...k]=1)，因为(<=k)直接用最优解走了。时间复杂度(O(n))。
相逢是问候
难度评分：省选+
题意是给你两种操作(0)和(1)，(0)是把([l,r])中的所有(a_i)替换成(C^{a_i})，其中(C)是一个给定常数；(1)是求(sum_{i=l}^r a_i)。
这个东西肯定是线段树维护，但是单纯的线段树肯定会(TLE)。想到花神游历各国那题，就是区间开方用线段树维护，是找到了区间开方下取整后几次这个数就变成了(0)这一方法进行优化。于是考虑(C^{a_i})有什么奇技淫巧。
(a_i)多次改变之后就成了这个样子：(C^{C^{C^{C^{C^{a_i}}}}})
由扩展欧拉定理得知(a^b ≡ a^{b mod varphi(p) + varphi(p)} (mod p))。
于是可以考虑递归求解，边界为(p=1)。
但是这还没完啊，我们如果每次都去递归求这个改之后的(a_i)还是(TLE)。
观察发现这个式子实际上在(logp)次之后值就一样了。为什么呢？考虑(varphi(p))的计算公式：(varphi(P)=P*pi_{i=1}^k frac{p_i-1}{p_i})，其中(p_i)表示(P)的每个质因子。若(P)为偶数，则(P)变成(varphi(p))至少要(÷2);若(P)为奇数，(p[i]-1)必存在偶数，于是(varphi(p))也为偶数。由此证明(logp)次后值就一样了。于是我们就像花神游历各国那题一样直接维护出现次数(Min)，一旦这个(Min)达到了边界我们就不继续进入子区间搞了。
一个优化就是预处理(C)的幂次方，把快速幂的(log)给去掉。于是时间复杂度为(O(nlog^2n))。
摧毁“树状图”
难度评分：省选+
题意是选出两条不相交的链，删去与这两条链相关的边，最大化连通块数量。
发现它有(x=0,1,2)三个(subtask)，其实会(x=0)就会(x=1,2)了。
考虑如何计算连通块个数：
(S)表示选出点的集合，(deg)表示点的度数，(edge)表示边，(lnk)表示链，(dot)表示点。
连通块个数(=sum_{i∈S} deg_i -sum edge imes 2 -lnk +1)。
然后由于边数(=)选出来点的个数(+)链数，化简一下式子得知连通块个数(=sum_{i∈S} deg_i -dots imes2 + lnk +1)。
知道这个我们就只用处理点和链了。
考虑(dp)。这个(dp)极其毒瘤要讨论很多。我看了(shadowice1984)神仙的题解啥也没看懂，全网搜了很多自己汇总一下，大概参考了(shadowice1984,Starria,Vixbob)三位神仙的博客。
现在有以下情况需要讨论：（假设当前子树的根为(u)，孩子节点为(v)）
·一条路径
·一条链
·一条路径+一条链
·讲不清，学(Starria)小姐姐画图
细节多的一批，慢慢讨论慢慢调吧(QwQ)。
寿司餐厅
难度评分：省选
题意是选择(i cdots j)的寿司可以获得(d_{i,j})的价值（(i leq j)），而选择了(x)就要付出(mx^2+cx)的价值，也就是获得(-mx^2-cx)的价值。最大化获得价值和。
由于权值不重复计算，我们可以考虑最大权闭合子图。
最大权闭合子图的经典模型：有一些物品，选择其中的每种都会获得相应价值(v_i)，但是有形如选(x)就要选(y)这样的限制关系，要求是最大化获得价值。（如果是最小化获得价值可以全部取相反数，仍是最大化的模型）。
这类问题一般使用最小割解决，即理想最优(-)调整代价。这个调整代价指的是调整为合法状态的代价。
考虑如何建图：基本模型是，对于一个点(i)，如果它的价值(v_i>0)，我们就把(S
ightarrow i)连一条边，流量为(v_i)，(i
ightarrow T)连一条边，流量为(0)，表示不选这个点需要付出(v_i)的代价；如果它的价值(v_i<0)，我们就把(i
ightarrow T)连一条边，流量为(-v_i)，(S
ightarrow i)连一条边，流量为(0)，表示选择这个点需要付出(-v_i)的代价。对于所有(x
ightarrow y)这样的限制关系，我们把(x
ightarrow y)连一条边，流量为(inf)，这样这条边就永远不会被割掉。
再考虑这题：首先发现这个记忆化是个幌子，假设方案①是拿([1,2],[2,3])，②是拿([1,3])，那么①会比②多花一个(a_2)的价值，所以一起选更划算。其次发现如果我们选择了(d_{i,j})，那么我们也要选择(d_{i+1,j})和(d_{i,j-1}),于是考虑把(d_{i,j})看成一个点，把这个看成限制关系。最关键的是处理代价(mx^2+cx)，看成“对于类型为(x)的寿司，每吃一个就要付出(x)的代价，吃过(x)后再吃还要付出(mx^2)的代价”。于是把每种寿司类型(x)也看成一个点，代价为(mx^2)，选择了(d_{i,i})就必须选择(a_i)。那么这就是最大权闭合子图问题模型了。