考虑分别计算恰有 $i$ 中颜色恰出现 $S$ 次的方案数，记为 $f_i$，则答案为 $\sum_{i=0}^{m}{f_i w_i}$。

直接算 $f_i$ 不好算，考虑至少有 $i$ 中颜色恰出现 $S$ 次的方案数，记为 $g_i$，显然，

$$g_i = C_{m}^{i} \frac{n!}{(n - iS)! (S!)^i} (m - i)^{n - iS}$$

式子中的三项分别表示： “选出 $i$ 种颜色”，“选位置让这 $i$ 种颜色恰出现 $S$ 次”，“其余的随便填剩下的颜色”。

这个式子是会算重的。具体的，对于一种恰有 $j(j \ge i)$ 种颜色恰出现 $S$ 次的方案，它在 $f_i$ 中会被算 $C_j^i$ 次。于是，

$$g_i = \sum_{j=i}^{m}{C^i_j f_j}$$

根据二项式反演有，

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

至此我们有了 $O(m^2)$ 的算法。

二项式反演是可以化成卷积形式的，

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

$$\rightarrow \quad f_i = \frac{1}{i!} \sum_{j=i}^{m}{\frac{j!}{(j-i)!} g_j (-1)^{j-i}}$$

下边懒得打这个 $\frac{1}{i!}$。

令 $A_i = i!g_i \, , \, B_i = \frac{(-1)^{i}}{i!}$ 则，

$$f_i = \sum_{j=i}^{m}{A_{j} B_{j-i}}$$

这里涉及差卷积，令 $A'_i = A_{m-i} \, , \, f'_i = f_{m-i}$ （也就是翻转）则，

$$f'_{m-i} = \sum_{j=i}^{m}{A'_{m-j} B_{j-i}}$$

再令 $t=j-i$ 有，

$$f'_{m-i} = \sum_{t=0}^{m-i}{A'_{m-i-t} B_{t}}$$

也就是，

$$f'_{i} = \sum_{t=0}^{i}{A'_{i-t} B_{t}}$$

这就是标准卷积形式，使用 $NTT$ 即可。$(1004535809=479 \times 2^{21} +1)$

值得注意的是，上述变形没有用到关于 $f_i$ 或 $g_i$ 的性质，于是对任何二项式反演均成立。

首先很容易想到差分约束

一个条件相当于 $x_i-x_j\le w(i,j)\iff x_i\le w(i,j)+x_j$，考虑从 $j$ 到 $i$ 连边，边权为 $w(i,j)$

考虑某个 $x_i-x_j$ 最小是多少，发现其实就是图中 $i\to j$ 的最短路的相反数。

因此，设 $\text{dis}(i,j)$ 表示 $i\to j$ 的最短路长度，那么我们只需要找到 $\min_{j\neq i}\text{dis}(i,j)$ 即可。

考虑分治。定义 $\text{solve}(l,r)$ 表示计算 $[l,r]$ 内每个点对 $[l,r]$ 内自己的贡献；设 $mid=(l+r)/2$，我们建一个源点 $s$ 并向每个 $x\in[l,mid]$ 连边，从 $s$ 开始跑 SPFA，就算出了 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。

同理也可以算出 $[mid+1,r]$ 到 $[l,mid]$ 的贡献；分治的边界是 $l=r$，此时直接返回即可。可以发现分治完成之后，我们就算出了 $[1,n]$ 中每个点的答案。

代码实现的方式大概是对每一位分 $0,1$ 考虑，和分治本质是等价的。

代码并不难写，不到 100 行，一张图就能截下来

COGS 不支持 Markdown，有些格式用不了，推荐到我的博客阅读。

Observation 1：从大到小，遇到 1 就操作，这样的操作次数最少。

证明：显然。

Observation 2：设上述结论得出的操作序列为 $p_1\sim p_m$，则对于每一次随机操作，如果操作的 $i\in p$，则 $m\gets m-1$，反之 $m\gets m+1$。

证明：因为操作顺序不影响结果，所以若 $i\in p$，则最少操作次数 -1。

反之手动模拟，如果 $i\notin p$，那么操作序列就要新增 $i$，操作次数 +1。

也就是说，答案只和 $m$ 的大小有关。

据此，设 $f_i$ 表示当前状态最少操作次数为 $i$ 时的期望答案。

有：

$$\begin{cases}f_i=i, & i\le k\\f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1, & \rm Otherwise\end{cases}$$

不知道有没有 MO 大神能解这个函数方程阿，反正我搞不出来这个东西，讲一下在洛谷题解里看到的神奇方法。

（upd：看到一种叫线性高消的神奇做法，算是高斯消元的变种，因为每个方程只有 3 项，所以可以 $\mathcal O(n)$ 算出来方程组的解）

考虑转化为更一般的形式，通常来讲期望递推都可以化简为 $f_i=f_{i-1}+b_i$ 的形式。

那么不妨设 $b_i=f_i-f_{i-1}$ 即 $f_i=f_{i-1}+b_i$，其中 $b_i$ 未知，把它带进方程解出来：

$$\begin{aligned}f_i & =\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1\\& = \frac{i}{n}(f_{i}-b_i)+\frac{n-i}{n}(f_i+b_{i+1})+1\end{aligned}$$

化简得：

$$b_i=\frac{(n-i)b_{i+1}+n}{i}$$

显然，$f_n=f_{n-1}+1$，故 $b_n=1$，先递推出 $b$，然后再推 $f$ 即可。

因为要求 $1\sim n$ 的约数，故时间复杂度为 $\mathcal O(n\ln n)$

感觉是比较基础的多项式题，但我还是因为弱智错误调了一晚上,wtcl。

令 $q$ 的下标为 $0$，以下均在 $(mod\ x^n)$ 意义下运算。

首先构造生成函数，有

\[ \sum_{i \ge 0} { E_i x^i } = \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} - \sum_{j>i}{ \frac{q_j}{(j-i)^2}} \; \Big] \; x^i } \]

\[ \qquad\qquad\qquad\qquad\;\;\, =  \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} \; \Big] \; x^i } - \sum_{i \ge 0} { \; \Big[ \; \sum_{j>i}{ \frac{q_j}{(j-i)^2}} \; \Big] \; x^i }\]

先看前半部分，有

\[ \sum_{i \ge 0} { \; \Big[ \; \sum_{j<i}{ \frac{q_j}{(i-j)^2}} \; \Big] \; x^i } = \sum_{i \ge 0} { \; \Big[ \; \sum_{j+k=i,k \gt 0}{ \frac{q_j}{k^2}} \; \Big] \; x^i } \]

\[ \qquad\qquad\qquad\qquad\qquad\quad\;\; = \Big[ \; \sum_{i \ge 0} { q_i x^i } \; \Big] \; \Big[ \; \sum_{i \gt 0} { \frac{1}{i^2} x^i } \; \Big] \]

对于后半部分，将 $q$ 翻转即可。

使用 $FFT$ 进行卷积，时间复杂度 $O(n \log n)$。

波特题。strong。

首先发现 A,B 之间互不影响，考虑枚举分割线 $i$，定义 $f(i)$ 表示以 $i$ 为结尾的 AA 串个数，$g(i)$ 表示以 $i$ 为开头的 AA 串个数。则答案为 $\sum\limits_{i=1}^{n-1} f(i)g(i+1)$。

然后发现直接 hash $\mathcal O(n^2)$ 求 $f(i),g(i)$ 就能拿 95pts，考场上就不用考虑正解了，直接冲 hash。但是练习还是要学一下的。

观察 AA 串中，两个 A 串的开头距离为 $|A|$。

考虑枚举 $w=|A|$，用一个波特才能想到的技巧：每隔 $w$ 撒一个点。这样每个 AA 串恰经过相邻两点。

设相邻两点分别为 $x,y$，定义 $\mathrm{lcp}(x,y)$ 表示以 $x,y$ 为开头的后缀的最长公共前缀，$\mathrm{lcs}(x,y)$ 表示以 $x,y$ 为结尾的前缀的最长公共后缀。

画个图就会发现，若有 AA 串经过 $x,y$，则必有 $\mathrm{lcp}(x,y)+\mathrm{lcs}(x,y)\ge w$，且这是 AA 串存在的充要条件。

然后又发现，$\mathrm{lcp}(x,y)+\mathrm{lcs}(x,y)$ 可能比 $w$ 大，此时有连续的一段点是 AA 串的开头/结尾，用两个差分数组维护即可。

时间复杂度：$\mathcal O(n(\log n+\ln n))$。

拒绝「命运」的安排。

小清新题。

这题给我最大的启示就是：不要被经验限制，开放思维，尝试不同的角度，一些平平无奇的性质可能就是解题的关键。

首先注意到，题目中的限制很可以容斥的样子。但事实上，如果一直将思维卡在容斥，这题就真的做不出来了。

我的思路比较清奇，我一开始想到的是 dp，将限制条件存入 $u$ 节点的 std::vector，然后一遍 dfs 算出来。

然而这样想同样存在一个问题，就是 $v$ 的分布不好处理。你会发现在这种思路中，我们几乎没办法确定方案。

归根结底是这样的 dp 过程能利用的有效信息太少，状态不好设计和转移。考虑正难则反。

不难发现，对于两组限制 $(u_1,v)$ 和 $(u_2,v)$，不妨设 $\mathrm{dep}(u_1)\le \mathrm{dep}(u_2)$，此时只用考虑 $u_2$ 的限制。

通过这个小思考，我们发现可以将此时还未处理到的最深的上节点的深度存入状态，进行转移。

令 $f(u,i)$ 表示处理了 $u$ 的子树，此时最深的未满足的限制的上节点深度为 $i$ 的方案数。

考虑加入一个子树，枚举 $u\to v$ 这条树边的权值：

权值为 1：则 $v$ 以上的限制全部被满足，最大深度仍由 $u$ 的子树提供，即 $f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{\mathrm{dep}(u)} f(v,k)$。

权值为 0：此时 $i$ 有可能是由 $u$ 的子树取到，也可能是由 $v$ 的子树取到，故 $f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{i}f(v,k)+f(v,i)\times \sum\limits_{k=0}^{i-1} f(u,k)$。

其中第二个和式上边界 -1 的原因是 $f(u,i)\times f(v,i)$ 已经在第一个和式中计算过，避免重复。

综上，$f(u,i)\gets f(u,i)\times \sum\limits_{k=0}^{\mathrm{dep}(u)} f(v,k)+f(u,i)\times \sum\limits_{k=0}^{i}f(v,k)+f(v,i)\times \sum\limits_{k=0}^{i-1} f(u,k)$。

直接 dp 可以获得 64pts，发现有效节点不多，把虚树建出来就可以获得 72pts，但我并不会建虚树。

（当然这题数据水，一部分出题人想不到的 $\mathcal O(n^2)$ 解法没被卡，甚至铃酱的 $\mathcal O(n^2\log n)$ 做法被放过去了，这很 CCF）

注意到这个 dp 的状态和深度有关，而且涉及求和，这正是线段树合并擅长的。

综上，使用线段树合并进一步优化 dp，时间复杂度 $\mathcal O(n\log \mathrm{dep})$，其中 $\rm dep$ 为深度最大的节点深度。