首先令 $a_n$ 为 $n$ 个奇点的奇树数量，类似的，定义 $b_n$ 为 $n$ 个偶点的偶树数量。

然后令 $A(x)=\sum_{i \ge 0}{a_ix^i}\ ,\ B(x)=\sum_{i \ge 0}{b_ix^i}$.

我们肯定是往根下面连若干个偶树使其成为奇树，或者是往根下面连若干个奇树使其成为偶树。

对于前者，枚举子树的大小，类似背包，可以得到：

$$A(x)=x\prod_{i \ge 1}{(1+x^i+x^{2i}+\dots)^{b_i}}$$

$$=x\prod_{i \ge 1}{(\frac{1}{1-x^i})^{b_i}}$$

乘 $x$ 是因为根本身是一个奇点。

于是：

$$\ln(A(x))=\ln(x)-\sum_{i \ge 1}{b_i\ln(1-x^i)}$$

两边求导：

$$\frac{A'(x)}{A(x)}=\frac{1}{x}+\sum_{i \ge 1}{ib_i\frac{x^{i-1}}{1-x^i}}$$

两边乘 $xA(x)$:

$$xA'(x)=A(x)+A(x)\sum_{i \ge 1}{ib_i\frac{x^i}{1-x^i}}$$

考虑第 $n$ 项系数：

$$na_n=a_n+\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j([x^{n-i}]\frac{x^j}{1-x^j})}}$$

而：

$$\frac{x^j}{1-x^j}=\sum_{i \ge 1}{x^{ij}}=\sum_{i \ge 1}{[j|i]x^i}$$

于是：

$$na_n=a_n+\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j[j|n-i]}}$$

也就是：

$$a_n=\frac{\sum_{i=1}^{n-1}{a_i\sum_{j=1}^{n-1}{jb_j[j|n-i]}}}{n-1}$$

再看后者，类似的，有：

$$B(x)=\prod_{i \ge 1}{(\frac{1}{1-x^i})^{a_i}}-1$$

$-1$ 是因为不存在 $0$ 个偶点的偶树。

类似得到：

$$b_n=\frac{\sum_{i=0}^{n-1}{(b_i+[i=0])\sum_{j=1}^{n}{ja_j[j|n-i]}}}{n}$$

这样就可以使用分治 $NTT$ 解决了，时间复杂度 $O(n\log^2n)$.

考虑分别计算恰有 $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$ 的性质，于是对任何二项式反演均成立。

感觉是比较基础的多项式题，但我还是因为弱智错误调了一晚上,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)$。

元音和辅音显然是独立的，我们考虑分开计算。记只用元音和辅音组成的单词数分别为 $ans_p$ 和 $ans_q$，则总答案为 $ans_p \times ans_q + ans_p + ans_q$。

考虑计算 $ans_p$，$ans_q$是类似的。枚举单词长度 $i$，显然有，

\[ ans_p = \sum_{i=1}^{n}{(i+1)p^i} = \frac{ p \frac{1-p^n}{1-p} + p -(n+1)p^{n+1}}{1-p} \]

这个式子可以 $O(\log n)$，但问题是 $1-p$ 不一定有逆元，所以是行不通的。

由于没有逆元，我们希望递推计算答案。

记 $f(n) = \sum_{i=1}^{n}{(i+1)p^i}$，整个式子是不好递推的，我们把它拆开，用 $p^i$ 和 $ip^i$ 去凑它。我们有，

\[ \left\{\begin{array}{l} f(i) = f(i-1) + (i+1)p^i = f(i-1) + ip^i + p^i\\ ip^i = p \times (i-1)p^{i-1} + p \times p^{i-1}\\p^i = p \times p^{i-1}\end{array}\right.\]

这样就可以构造矩阵了。

\[ \begin{bmatrix} f(i-1)\\ (i-1)p^{i-1}\\ p^{i-1} \end{bmatrix}  \begin{bmatrix} 1 & p & 2p\\ 0 & p & p\\ 0 & 0 & p \end{bmatrix} = \begin{bmatrix} f(i)\\ ip^i\\ p^i \end{bmatrix} \]

时间复杂度$O(\log n)$。

搜不到题解啊，自己随便写一篇玩。

如果直接求亮灯数的期望 $E$，这是不好处理的，因为我们不可能把所有灯的亮暗同时放入到状态中。

不妨换一个角度，去分别考虑每个灯最终的状态。考虑计算坐标$(x,y,z)$的灯最终亮着的概率 $P_{x,y,z}$，那么它有 $P_{x,y,z}$ 的概率给答案贡献 $1$，即 $E=\sum{p_{x,y,z}}$。

接下来的问题是如何计算 $P_{x,y,z}$。

首先考虑任选 $A,B$ 能包含 $(x,y,z)$ 的概率（以下简记为 $P_{cr}$），不难得到 $P_{cr}=\frac{2x(n-x+1)-1}{n^2}\frac{2y(m-y+1)-1}{m^2}\frac{2z(p-z+1)-1}{p^2}$。

一种直接的想法是DP。设 $f_{i,x,y,z,0/1}$ 表示 $i$ 次操作后，$(x,y,z)$ 暗/亮的概率，转移显然：

$f_{i,x,y,z,0/1}=P_{cr}f_{i-1,x,y,z,1/0}+(1-P_{cr})f_{i-1,x,y,z,0/1}$

第一维可以滚，时间复杂度$O(nmpk)$，寄了。

仔细想想其实不用DP，一盏灯最终是亮的，那么它可能被操作 $1,3,5,...$ 次，即 $P_{x,y,z}=val(1)+val(3)+val(5)+...$，其中 $val(i)$ 表示恰好被操作 $i$ 次的概率。

$val(i)$ 怎么算？其实就是从 $k$ 次操作中选出 $i$ 个包含它，即 $val(i)=C^{i}_{k}P_{cr}^i(1-P_{cr})^{k-i}$。

整理一下，$P_{x,y,z}=C^{1}_{k}P_{cr}(1-P_{cr})^{k-1}+C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+...$

经典二项式定理。

$[(1-P_{cr})+P_{cr}]^k=C^{0}_{k}(1-P_{cr})^{k}+C^{1}_{k}P_{cr}^1(1-P_{cr})^{k-1}+C^{2}_{k}P_{cr}^2(1-P_{cr})^{k-2}+C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+... (\alpha)$

$[(1-P_{cr})-P_{cr}]^k=C^{0}_{k}(1-P_{cr})^{k}-C^{1}_{k}P_{cr}^1(1-P_{cr})^{k-1}+C^{2}_{k}P_{cr}^2(1-P_{cr})^{k-2}-C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+... (\beta)$

于是$P_{x,y,z}=\frac{\alpha-\beta}{2}=\frac{1-(1-2P_{cr})^k}{2}$

这样就整完了。时间复杂度$O(nmp\log k)$，其中$\log k$为快速幂。

首先不难想到BFS。

以及，箱子能被推动到目标方向当且仅当：①目标方向是空地；②目标方向关于箱子的对面是空地，且人能到达。

如果允许人在空地上任意传送，本题将会简单很多。令 $f_{i,j}$ 表示箱子到达 $(i,j)$ 时的最小次数，每次转移只需判断目标方向的对面是否是空地即可。

但有了沉重货物的限制，会导致人并不一定能到达箱子旁的空地（即使初始时他可以到达）。

不过不难发现，当人推动一次箱子时，他将会“取代”箱子原本的位置。也就是说，判断人是否能到达空地，实际上是判断箱子上次的位置是否能到达那里。而方向只有四个，令 $f_{i,j,0/1/2/3}$ 表示箱子到达 $(i,j)$ ，且上次它在现在的 上/下/左/右 时的最小次数。每次转移时，从上次的位置出发进行搜索，判断是否能到达目标方向对面的空地即可。

时间复杂度大常数$O(n^4)$，无法通过。

上述算法的瓶颈在于，每次转移时都要进行一次搜索，包含了大量的重复计算。我们希望通过一些预处理优化这一过程。

实际上已经很明显了。我们把每个空地抽象成点，向四周的空地连边。箱子放于 $(x,y)$ 时人无法从 $(a,b)$ 到达 $(c,d)$ ，实际上就是说 $(x,y)$ 是原图的一个割点，将 $(a,b)$ 所在连通块与 $(c,d)$ 所在连通块分离。相反，若 $(a,b)$ 与 $(c,d)$ 在同一连通块中，人肯定能相互到达。这样，通过预处理原图的相关$dcc$信息，我们可以做到$O(1)$的转移。

关于 $f$ 的初始化，需要从人的出发点单独搜一次，记录初始时人能到达的箱子旁的空地。

码量稍大，不过每一部分相对简单。