AGC005 题解
比赛链接
题目评分：1054-1828-1976-2943-3276-3440
A STring
水题，直接用个栈，不断处理一下即可。
B Minimum Sum
经典题，数据结构各显神通，肯定得枚举一个位置算贡献。
Solution
算法一
我没有脑子，这题直接线段树一下，做一遍二分，二分出每一个位置所能成为答案的最大左右区间，乘法原理计数即可。
时间复杂度 \(O(n\log^2n)\)。
算法二
我学习过单调栈，这题不是单调栈裸题吗。
记录每个数踢出去的数的个数，那么当前数的向前的最多可延展的区间也可以出来，类似的，向后的最多可延展的区间个数也可以出来。
时间复杂度 \(O(n)\)。
C Tree Restoring
Solution
智商题，没有智商的 cnyz 被区分了。考虑 \(a_i\) 的最大值是如何来的，显然是一条直径，那么，\(\min a_i\ge \max a_i\)。
容易想到，如果 \(\max a_i\) 是奇数，那么最小点得有两个，同理，\(\max a_i\) 为偶数时，最小点得有一个，同时，\(a_i\) 除了最大值和最小值，之间的至少有 \(2\) 个。
那么这些都判一下就行了，时间复杂度 \(O(n)\)。
D ~K Perm Counting
Solution
正着求很不好求，考虑容斥。显然可以将原本的不能选的关系抽象成一个二分图，那就是会变成若干条链，且相邻的边不能取，将链拍平到序列上考虑 DP。
设 \(f_{i,j,0/1}\) 表示现在在第 \(i\) 位选了 \(j\) 条边，且当前这条边选了或没选，有转移：
\[f_{i,j,0}=f_{i-1,j,0}+f_{i-1,j,1}\\f_{i,j,1}=f_{i-1,j-1,0} \]直接暴力 dp，可以做到 \(O(n^2)\) 的时间复杂度，注意判当前是不是链头。
好像用多项式可以优化到 \(O(n\log n)\)？不过我不会。
E Sugigma: The Showdown
Solution
博弈好题。考虑什么时候会陷入无限循环，称一条树 \(a\) 上的边 \((u,v)\) 是横跳边，当且仅当 \(\text{dist}_b(u,v)\ge 3\)，这是不需要证明的。
容易发现，我们可以处理出所有可达的点，容易使用 dfs 解决，只需要比较某个点到两个起始点的距离。
如果在可达的点组成的连通块中出现了横跳边，那么可以无限循环，否则的话，A 想让轮数最多，那只能到一个距离出发点最远的点来等死，容易发现轮数是最大的。
时间复杂度 \(O(n)\)。
F Many Easy Problems
Solution
考虑枚举每个点算贡献，容易发现： \[f(i)=\sum^n_{u=1}\binom{n}{i}-\sum_{v\in son(u)}\binom{siz_v}{i} \]其中 \(son(u)\) 表示与 \(u\) 相连的节点集合，\(siz_u\) 表示子树大小。
可以看做是枚举每一个点，用所有答案减去不包含的答案。
化柿子：
\[f(i)=n\binom{n}{i}-\sum^n_{u=1}\sum_{v\in son(u)}\binom{siz_v}{i} \]接着化简后面这一坨：
\[\sum^n_{u=1}\sum_{v\in son(u)}\binom{siz_v}{i}\\\sum^n_{j=i}cnt_j\binom{j}{i} \]其中 \(cnt_i\) 表示 \(siz=i\) 的子树出现了几次。
拆掉组合数：
\[\frac 1 {i!}\sum^n_{j=i}\frac{cnt_j(j!)}{(j-i)!}\\\frac 1 {i!}\sum^{n-i}_{j=0}\frac{cnt_{j+i}(j+i)!}{j!} \]后面的柿子是一个卷积形式，令 \(F_i=cnt_ii!\)，\(G_i=\frac {1}{i!}\)，那么：
\[\frac 1 {i!}\sum^{n-i}_{j=0}F_R(n-i-j)G_j \]使用 FFT 优化，时间复杂度 \(O(n\log n)\)。
顺带说一句，\(924844033\) 的原根为 \(5\)。