【x义x讲坛】生成函数再入门

因为作者会了一些多项式板子所以就回来写这篇博客了蛤蛤蛤 ### **[P4841 城市规划](https://www.luogu.org/problem/P4841)** 定义$f[n]$为$n$个点的**简单无向连通图**数量，而 $g[n]$ 为 $n$ 个点的**简单无向图**数量。显然对于一个简单无向图，每两个点有连边和不连边两种情况，于是有 $$g[n]=2^{\begin{pmatrix}n\\2\end{pmatrix}}$$ 我们也可以把$1$号节点所在连通块大小分类讨论： 如果$1$号节点所在连通块大小为 $x$，那么我们可以再选出 $x-1$ 个节点（$n-1\choose x-1$）来决定$1$所在连通块有哪些节点，然后对于这个连通块内部有 $f[x]$ 种情况，对于这个连通块外部则是 $g[n-x]$ 种情况。 于是，$1$号节点连通块大小为 $x$ 的，节点数为 $n$ 的简单无向图的个数显然为 $$\begin{pmatrix}n-1\\x-1\end{pmatrix}f[x]g[n-x]$$ 于是有 $$g[n]=\sum_{x=1}^n\begin{pmatrix}n-1\\x-1\end{pmatrix}f[x]g[n-x]$$ 把 $g[n]=2^{\begin{pmatrix}n\\2\end{pmatrix}}$ 代回去，组合数也拆掉 $$\dfrac{2^{\begin{pmatrix}n\\2\end{pmatrix}}}{(n-1)!}=\sum_{x=1}^n\dfrac{f[x]}{(x-1)!}\dfrac{2^{\begin{pmatrix}n-x\\2\end{pmatrix}}}{(n-x)!}$$ 设 $a[i]=\dfrac{f[i]}{i!}$，其普通型生成函数为 $A(x)$；设 $b[i]=\dfrac{2^{\begin{pmatrix}i\\2\end{pmatrix}}}{i!}$，其普通型生成函数为 $B(x)$。（其实既然 $a[i]$ 的分母里有个 $i!$，你把 $A[i]$ 理解成 $f[i]$ 的指数型生成函数也没问题） 显然 $i*a[i]$ 的生成函数为 $xA'(x)$，$i*b[i]$ 的生成函数为 $xB'(x)$。则有 $$xB'(x)=xA'(x)*B(x)$$ $$A(x)=\int\dfrac{B'(x)}{B(x)}$$ $A(x)$ 就是 $\ln B(x)$。$B(x)$ 完全已知，套个板子即可。 ### **[CF438E The Child and Binary Tree](https://www.luogu.org/problem/CF438E)** 根节点可以任意选权值，于是枚举左子树权值和。 $$f[n]=\left(\sum_{c[i]\in S}\sum_{x=0}^n f[x]*f[n-c[i]-x]\right)$$ 但是注意，$f[0]=1$。 于是设 $f[n]$ 的普通型生成函数为 $F(x)$，$C(x)=\sum_{c[i]\in S}x^{c[i]}$。则显然有 $$F(x)=C(x)F^2(x)+1$$ $+1$ 就是为了特判 $f[0]$。 易解得 $$F(x)=\dfrac{1\pm\sqrt{1-4C(x)}}{2C(x)}$$ $$F(x)=\dfrac{2}{1\pm\sqrt{1-4C(x)}}$$ 把$x=0$代进去可以知道取正号。 ### **[P4451 [国家集训队]整数的lqp拆分](https://www.luogu.org/problem/P4451)** 显然有： $$g[n]=\begin{cases}\sum_{i=0}^n f[i]*g[n-i]&(n\neq 0)\\1&(n=0)\end{cases}$$ 设其普通型生成函数为$G(x)$，斐波那契数列的生成函数是$F(x)=\dfrac{x}{1-x-x^2}$，则有 $$G=G*F+1$$ $$G=\dfrac{1-x-x^2}{1-2x-x^2}$$ $$G=1+\dfrac{x}{1-2x-x^2}$$ $$G=1+\frac{\sqrt 2}{2}\left(\dfrac{1}{1-(1+\frac{\sqrt 2}2)x}-\dfrac{1}{1-(1-\frac{\sqrt 2}2)x}\right)$$ 所以 $$g_n=\dfrac{(\sqrt 2+1)^n-(-\sqrt 2+1)^n}{2\sqrt 2}$$ 然后找个根号2就出来了。根号2=59713600。（怎么题解里都是$O(N)$递推啊） ### **[P4491 [HAOI2018]染色](https://www.luogu.org/problem/P4491)** 容斥在数数题里面始终是非常重要的一个思想。 当出现次数为 $S$ 的颜色恰好有 $K$ 种的时候，会有 $W[k]$ 的贡献。我们进行容斥，希望计算出现次数为 $S$ 的颜色**至少**$K$种的方案数。 先钦定 $K$ 种颜色（为了选择这 $K$ 种颜色要贡献 $M\choose k$）出现次数为 $S$。（后面我们可能会在类似问题上使用“至少 $K$ 种颜色出现次数为 $S$ ”的表述，它指的是上面那句话而不是它的字面意思！）这 $K$ 种颜色会占掉 $KS$ 个格子，还剩 $N-KS$ 个空格。我们把钦定的每种颜色各看成一种物品，空格也看作单一一种物品，于是这是一个多重集排列问题，方案数为 $$\dfrac{N!}{(S!)^K(N-KS)!}$$ 对于这 $N-KS$ 个空格，每个空格还可以随便填一种没被钦定的颜色，方案数为 $(M-K)^{N-KS}$。 于是答案就是： $$f[K]=\begin{pmatrix}M\\K\end{pmatrix}\dfrac{N!}{(S!)^K(N-KS)!}(M-K)^{N-KS}$$ emmm有点恶心但毕竟能搞。 容斥一下，**恰好** $K$ 种的方案数则为 $$ans[K]=\sum_{j=K}^M(-1)^{j-K}\begin{pmatrix}j\\i\end{pmatrix}f[j]$$ （这个柿子是哪里来的呢？对于一种恰好 $K$ 种的方案，它会被 $f[j]$ 统计 $k\choose j$ 次，于是使用一下二项式反演即可得上面的柿子） 组合数拆掉，又因为打大写的 $K$ 需要按shift很不方便所以我们把它换成 $i$。（？？？） $$i!\cdot ans[i]=\sum_{j=i}^M\dfrac{(-1)^{j-i}}{(j-i)!}\cdot(j!\cdot f[j])$$ 记 $g[i]=(M-i)!f[M-i]$。 $$i!\cdot ans[i]=\sum_{j=i}^M\dfrac{(-1)^{j-i}}{(j-i)!}\cdot g[M-j]$$ 改成枚举 $j-i$ 会比较好看。 $$i!\cdot ans[i]=\sum_{x=0}^{M-i}\dfrac{(-1)^x}{x!}\cdot g[M-i-x]$$ 好了，得到卷积形式。 ### **[P4389 付公主的背包](https://www.luogu.org/problem/P4389)** 因为物品数量肯定是够的，所以可以认为它们都有无限个。于是可以把其普通型生成函数简单地写成$\dfrac{1}{1-x^{v[i]}}$。 但是把$n$个这种玩意乘起来的复杂度我们怎么样都是受不了的，所以我们可以考虑一下把乘法转化成取对数后的加法。 问题就是$\ln\dfrac 1{1-x^v}$是啥。显然它是$-\ln{(1-x^v)}$。如果您是像$\color{black}\texttt{q}\color{red}\texttt{iyang2004}$一样的数学大师的话，您应该知道 $$\ln(1+x)=x-\dfrac{x^2} 2+\dfrac{x^3} 3-\dfrac{x^4}4+\dots$$ 从而显然有 $$\ln\dfrac{1}{1-x^v}=x^v+\dfrac{x^{2v}}{2}+\dfrac{x^{3v}}{3}+\dots$$ 对于所有体积为$v$的物品（可能有多种，我们一起贡献，否则复杂度就假了），我们都直接暴力$O(\dfrac{M}{v})$贡献系数。众所周知这个过程是$M\log M$的。然后exp回去即可。 ## **[P5900 无标号无根树计数](https://www.luogu.com.cn/problem/P5900)** 因为不会这题被 $\texttt{R}\color{red}\texttt{ealSpongeBob}$ 给 D 爆了/dk 首先介绍一下一个挺有用的东西：$\text{Euler}$ 变换。 众所周知，对一个生成函数 $F$ 做 $\text{Exp}$ 得到的生成函数的意义是：把 $n$ 分成若干无序组，每一个大小为 $i$ 的组都有 $[x^i]F$ 个方案。 而 $\text{Euler}$ 变换的含义与其类似，但是大小相同方案相同的两个组要求无序。 这个要求有点奇怪。所以可以想到枚举大小和每个方案，这时我们只能决定使用多少个这种方案（要求我们不考虑它们的顺序），所以 $\text{Euler}$ 变换即 $$\prod_{i}\prod_{j=1}^{f_i}(1+x^i+x^{2i}+\dots)$$ 整理得 $$\prod_{i=1}^{\infty}(1-x^i)^{-f_i}$$ （不得不说生成函数真的是数数困难患者的福音，原来见到“无标号”这三个字我只能懵 B，现在拿 $\text{Euler}$ 变换刚就好了） 一顿 $\ln$ 再 $\exp$ 后得到 $$\text{Exp} \sum_{i}\dfrac{F(x^i)}{i}$$ 可以 $O(n\log n)$ 计算了。当然也可以通过等价类计数的那套理论得到相同的结论。 无标号有根树计数也就立刻解决了，只需要解 $$F(x)=x\text{Exp} \sum_{i}\dfrac{F(x^i)}{i}$$ 可以使用分治 FFT 或者多项式牛迭。虽然后者复杂度少一个 log 但是由于要做万恶的 Exp 所以反而没有分治 FFT 快。 分治 FFT 的做法如下：两边求导得 $$F'(x)-x^{-1}F(x)=F(x)\cdot\sum_{i=1}x^{i-1}F'(x^i)$$ $$xF'(x)=F(x)+F(x)\cdot\sum_{i=1}x^{i}F'(x^i)$$ 设 $$G(x)=\sum_{k}x^kF'(x^k)$$ 容易知道 $$g_i=\sum_{d|i}df_d$$ 和 $$f_i=\dfrac{\sum_{j=1}f_jg_{i-j}}{i-1},f_1=1$$ 就可以愉快地分治 FFT 了。（但实际细节很鬼畜） 问题是无标号无根树计数怎么办……我们需要一个在同一个无根树中唯一的节点作为根。下面使用重心。 解决方式也很简单，直接用按有根树算出的方案数减去当前节点不是重心的方案数。 $$ans_i-\sum_{j=\frac n 2 +1}^{n-1} ans_jans_{n-j}$$ 但是当 $n$ 为偶数的时候，可能会出现一棵树有两个重心的情况，一般会被统计两次，但是如果断掉两个重心之间的边后形成的两个子树完全一样它又只会被统计一次。总的来说应该减去 $$f_{\frac n 2}\choose 2$$ ### Euler 变换的群论证明 首先枚举儿子数 $i$。考虑应用 burnside 引理，显然一个置换 $f$ 的不动点只与其循环拆分（有序，显然循环间可以通过最前一个元素的位置分出顺序） $\{a_i\}$ 有关。具体来说是 $$\sum_{i}\dfrac{1}{i!}\sum_{f}\prod F(x^{a_i})$$ （解释一下上式：循环内所有组的“染色”方案必须完全一样，选择大小均为 $s$ 方案数就只有 $[x^s]F$，但是“占地”却是 $a_is$，故有上式） （似乎也叫做生成函数形式的 Polya 定理？） 思考有多少个循环能被循环拆分 $\{a_i\}$ 描述。首先决定每个标号属于哪个循环，然后循环内可以圆排列，而这样搞会破坏循环原本的有序，所以还要再除以循环数的阶乘。 $$\sum_{i}\dfrac 1{i!}\sum_{l,\sum a_j=i}\dfrac 1{l!}{i\choose a_1,a_2,...a_l}\prod_{j=1}^lF(x^{a_i})(a_i-1)!$$ $$\sum_{i}\sum_{l,\sum a_j=i}\dfrac{1}{l!}\prod_{j=1}^l\dfrac{F(x^{a_i})}{a_i}$$ 我们发现现在后面这个部分可以写成 $\text{Exp}$ 的形式。设 $$G(x,y)=\sum_{i=1}^{\infty}\dfrac{F(x^i)y}{i}$$ 则我们得到 $$\sum_{i}[y^i]e^{G}$$ 直接带入 $y=1$ 即可。我们得到 $$\text{Exp}\left(\sum_{i=1}^{\infty}\dfrac{F(x^i)}{i}\right)$$ 即 Euler 变换。 ### **[P3784 [SDOI2017]遗忘的集合](https://www.luogu.org/problem/P3784)** 很套路地知道 $$f(x)=\prod_{i\in S}\dfrac 1{1-x^i}$$ 和上一题一样$\ln$并展开 $$\ln f(x)=\sum_{i\in S}\sum_{k=1}^\infty \dfrac{x^{ki}}{k}$$ 这时候神仙操作来了，我们改为枚举$ik=T$ $$\ln f(x)=\sum_{T=1}^\infty \dfrac{x^T}T\sum_{i|T}i[i\in S]$$ 这样，如果我们知道$\ln f(x)$的系数表示，我们就能知道 $$\sum_{i|T}i[i\in S]$$ 然后反演一下就行了。 ### **[P4705 玩游戏](https://www.luogu.org/problem/P4705)** 答案就是 $$\sum_{i=1}^n\sum_{j=1}^m(a_i+b_j)^k$$ 除以$nm$。 显然这个鬼样子没法做的，拆开k次方 $$\sum_{i=1}^n\sum_{j=1}^m\sum_{d=0}^kC_k^da_i^db_j^{k-d}$$ 把$d$换到前面 $$\sum_{d=0}^kC_k^d\sum_{i=1}^na_i^d\sum_{j=1}^mb_j^{k-d}$$ 如果我们已经求出$A(d)=\sum_{i=1}^na_i^d,B(d)=\sum_{i=1}^mb_i^d$，那么答案就是 $$\sum_{d=0}^kC_k^dA(d)B(k-d)$$ $C_k^d$里面有$d!$和$(k-d)!$，刚好可以和$A(d),B(k-d)$配在一起，于是拆掉 $$k!\sum_{d=0}^k\dfrac{A(d)}{d!}\cdot\dfrac{B(k-d)}{(k-d)!}$$ 好了，变成卷积形式了。但是问题是，$A(d)$怎么求？ 这是一个很难想出来的经典问题。 考虑一个多项式 $$F(x)=\prod_{i=1}^n(a_ix+1)$$ 这个东西可以分治求，即前一半乘后一半。复杂度我不会算但反正是对的。 然后取一个$\ln$并展开。 $$\ln F(x)=\sum_{i=1}^n\ln(a_ix+1)$$ $$=\sum_{i=1}^n\sum_{j=1}^\infty-\dfrac{(-a_ix)^j}j$$ $j$换到前面 $$=\sum_{j=1}^\infty-\dfrac{(-x)^j}j\sum_{i=1}^na_i^j$$ $$=\sum_{j=1}^\infty-\dfrac{(-1)^jA(j)}{j}x^j$$ ！！！然后就好了。 然后是$\color{black}\texttt{q}\color{red}\texttt{iyang2004}$钦定很水的三道题。 $\color{black}\texttt{q}\color{red}\texttt{iyang2004}$：真的很水的，你看一下 ### **[P5401 [CTS2019]珍珠](https://www.luogu.org/problem/P5401)** 大意就是每种颜色出现的次数整除2，再全部加起来大于等于m。 稍微转化一下就是：设$d[i]$是颜色$i$出现的次数， $$\sum_{i=1}^D(d[i]~\text{mod}~2)\le n-2m$$ 设等式左边这个东西叫 $cnt$。下面求 $cnt=k$ 的方案数 $f_k$。 它等于 $$\begin{pmatrix}D\\k\end{pmatrix}\dfrac{1}{2^{D}}[x^n](e^x+e^{-x})^{D-k}(e^x-e^{-x})^k$$ $$\begin{pmatrix}D\\k\end{pmatrix}\dfrac{1}{2^{D}}[x^n]e^{-Dx}(e^{2x}+1)^{D-k}(e^{2x}-1)^k$$ 暴力展开： $$(e^{2x}+1)^{D-k}=\sum_{i=0}^{D-k}\begin{pmatrix}D-k\\i\end{pmatrix}e^{2ix}$$ $$(e^{2x}-1)^k=\sum_{i=0}^k\begin{pmatrix}k\\i\end{pmatrix}(-1)^{k-i}e^{2ix}$$ 那么 $$[x^n]e^{-Dx}(e^{2x}+1)^{D-k}(e^{2x}-1)^k$$ 等于 $$[x^n]\sum_{i=0}^{D}e^{(2i-D)x}\sum_{j=0}^i\begin{pmatrix}D-k\\i-j\end{pmatrix}\begin{pmatrix}k\\j\end{pmatrix}(-1)^{k-j}$$ ……算到这里不会了/dk 我们的策略是改为算 $g_i=$ $$\begin{pmatrix}D\\k\end{pmatrix}\dfrac{1}{2^{k}}[x^n]e^{(D-k)x}(e^x-e^{-x})^{k}$$ 通过式子可以发现我们对 $(D-k)$ 种颜色放松了限制。这个玩意有什么实际意义呢，答案是对于 $f_j$ 它会被 $g_i$ 统计 $j\choose i$ 次，即 $g_i=\sum_{j}\begin{pmatrix}j\\i\end{pmatrix}f_j$，可以反演回 $f$： $$\begin{aligned}f_i&=\sum_{j}(-1)^{j-i}\begin{pmatrix}j\\i\end{pmatrix}g_j\\&=\dfrac{1}{i!}\sum_{j}\dfrac{(-1)^{i-j}}{(j-i)!}(j!g_j)\end{aligned}$$ 是卷积形式。 下面化简 $g_k$： $$\begin{pmatrix}D\\k\end{pmatrix}\dfrac{1}{2^{k}}[x^n]e^{(D-k)x}(e^x-e^{-x})^{k}$$ $$\begin{pmatrix}D\\k\end{pmatrix}\dfrac{1}{2^{k}}[x^n]e^{(D-2k)x}(e^{2x}-1)^k$$ $$\begin{pmatrix}D\\k\end{pmatrix}\dfrac{1}{2^{k}}[x^n]\sum_{j=0}^k\begin{pmatrix}k\\j\end{pmatrix}(-1)^{k-j}e^{(D-2k+2j)x}$$ $$\begin{pmatrix}D\\k\end{pmatrix}\dfrac{1}{2^{k}}\sum_{j=0}^k\begin{pmatrix}k\\j\end{pmatrix}(-1)^{k-j}(D-2k+2j)^n$$ 容易发现也是卷积形式： $$\dfrac{D!}{(D-k)!}\dfrac{1}{2^{k}}\sum_{j=0}^k\dfrac{1}{j!}\dfrac{(-1)^{k-j}(D-2k+2j)^n}{(k-j)!}$$ ### **[P5293 [HNOI2019]白兔之舞](https://www.luogu.org/problem/P5293)** $n\le 3$ 的数据范围显然是需要利用的。3,4,5,6 号测试点都有 $n=1$，于是先试着分析一下 $n=1$ 的情况。 设 $f_{i,j}$ 是走到第 $i$ 行，步数为 $j$。 $$f_{i,j}=w[1][1]\sum_{d=0}^{i-1}f_{d,j-1}$$ 容易得到 $$f_{i,j}=w[1][1]^j\begin{pmatrix}i-1\\j-1\end{pmatrix}$$ $$ans_t=\sum_{i=0}^L\sum_{j\bmod k=t} w[1][1]^j\begin{pmatrix}L-1\\j-1\end{pmatrix}$$ $$ans_t=\sum_{j\bmod k=t} w[1][1]^j\begin{pmatrix}L\\j\end{pmatrix}$$ 运用单位根反演： $$\dfrac 1 n\sum_{k=0}^{n-1} \omega_{n}^{vk}=[v\bmod n=0]$$ 得到 $$ans_t=\dfrac 1 k\sum_{j=0}^L w[1][1]^j\begin{pmatrix}L\\j\end{pmatrix}\sum_{d=0}^{k-1}\omega_{k}^{d(j-t)}$$ 传 统 艺 能（指换求和号） $$ans_t=\dfrac 1 k\sum_{d=0}^{k-1}\omega_{k}^{-dt}\sum_{j=0}^L\begin{pmatrix}L\\j\end{pmatrix}(w[1][1]\omega_{k}^d)^j$$ 后面那个 sigma 用二项式定理。 $$ans_t=\dfrac 1 k\sum_{d=0}^{k-1}\omega_{k}^{-dt}(w[1][1]\omega_k^d+1)^L$$ $(w[1][1]\omega_k^d+1)^L$ 计算代价是 $O(K\log)$ 的，直接求就是了，设为 $a_d$。 $$ans_t=\dfrac 1k\sum_{d=0}^{k-1}\omega_{k}^{-dt}a_d$$ 这不是逆 FFT 吗！ ……然而 $k$ 不一定是 2 的幂，无法正常 FFT。 如果你知道 [Bluestein 算法](https://xyix.github.io/2019/10/03/%E3%80%90x%E4%B9%89x%E8%AE%B2%E5%9D%9B%E3%80%91%E3%80%90%E6%90%AC%E8%BF%90%E3%80%91%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%EF%BC%88%E4%B8%8A%EF%BC%89/#Bluestein%E7%AE%97%E6%B3%95)，那么下面这一步操作就不太神仙了： $$ans_t=\dfrac 1k\omega_k^{t\choose 2}\sum_{d=0}^{k-1}\omega_{k}^{d\choose 2}a_d\cdot\omega_{k}^{-{t+d\choose 2}}$$ 也就是把 FFT 转化成一次卷积。 （为什么不用博客链接里的拆分方法？因为此题单位根不一定有二次剩余） $n=3$ 的情况只是把 $w[1][1]$ 换成一个矩阵 $W$。原来的柿子改成 $B\times\text{原柿}$ 的 $[1][y]$ 处的值。$B$ 是一个 $1\times N$ 的矩阵，只在 $[1][x]$ 处为 1，其他位置为 0。 那么把 $a_d$ 改成 $(B\times(\omega_{k}^dW+I)^L)[1][y]$ 即可。 ### **[P5206 [WC2019] 数树](https://www.luogu.org/problem/P5206)** ~~请你用数数方法数出在树和树上给鼠赋予数的方案数。~~ 直观地讲，两棵树 $T_r,T_b$ 每有一条边重叠，那么就会有一个鼠失去选择，于是**第一问**答案是 $$y^{n-|T_r\cap T_b|}$$ 这非常 sb。 下面为了方便直接称我们求的是 $y^{-|T_r\cap T_b|}$。 **第二问** 求： $$\sum_{T_r}y^{-|T_r\cap T_b|}$$ 交集符号简直不可能处理。改为枚举 $T_r\cap T_b=S$。 $$\sum_{S\subseteq T_b} y^{-|S|}\sum_{T_r} [T_r\cap T_b=S]$$ 看上去稍微好处理了一点但还是不够。 $$\sum_{T}[T\cap T_b=S]=\sum_{S\subseteq R\subseteq T_b}(-1)^{|R|-|S|}\sum_{R\subseteq T}$$ 遇事不决，换求和号： $$\sum_{R\subseteq T_b}\text{cnt}(R\subseteq T)\cdot(-1)^{|R|}\cdot \sum_{S\subseteq R}(-y)^{-|S|}$$ 啊，清爽多了。 再来！枚举 $|S|$！ $$\sum_{R\subseteq T_b}\text{cnt}(R\subseteq T)\cdot(-1)^{|R|}\cdot \sum_{i=0}^{|R|}(-y)^{-i}\begin{pmatrix}|R|\\i\end{pmatrix}$$ 二项式定理： $$\sum_{R\subseteq T_b}\text{cnt}(R\subseteq T)\cdot (\dfrac 1 y-1)^{|R|}$$ 好了现在的问题就是怎么求 $\text{cnt}(R\subseteq T)$。 假设图原来为空，我们加入 $R$，此时有 $q$ 个联通块每个大小都是 $a_i$，容易猜到 $$\text{cnt}(R)=N^{q-2}\prod a_i$$ （事实上矩阵树定理爆解行列式也可以得出同样结果） （也可以用 Prufer 序列证明但我不会） $R$ 无环，所以其每条边都会使得联通块减少一个。所以原式变成 $$\sum_{R\subseteq T_b}N^{N-2-|R|}\cdot (\dfrac 1 y-1)^{|R|}\cdot \prod a_i$$ $$\dfrac {(\dfrac 1 y-1)^N}{N^2}\sum_{R\subseteq T_b}(\dfrac {Ny}{1-y})^{N-|R|}\cdot \prod a_i$$ $$\dfrac {(\dfrac 1 y-1)^N}{N^2}\sum_{R\subseteq T_b}\prod \dfrac {Ny}{1-y}a_i$$ $a_i$ 看上去不能再形式化地推柿子来得到结果了。考虑 DP。 设 $f_{i,j}$ 是只考虑 $i$ 的子树，且 $i$ 所在联通块大小为 $j$ 时，但是去掉 $i$ 所在联通块权值的权值和。 直接转移是 $N^2$ 的，但是转移是卷积的形式，每次多考虑 $u$ 的一个儿子 $v$ 时 $$f_{u,j}=f_{u,j}\sum_k \dfrac {Ny}{1-y}kf_{v,k}+\sum_{k}f_{u,j-k}f_{v,k}$$ 所以有 $$F_u(x)=\dfrac {Ny}{1-y}F_v'(1)F_u(x)+F_v(x)F_u(x)$$ 真的去做求导就意味着我们必须记住整个多项式，需要避免。 实际上最终要求的也就是 $\dfrac {Ny}{1-y}F_1'(1)$，所以设 $g_u=F_u'(1)$。 $$g_u=\dfrac {Ny}{1-y}g_vg_u+g_vF_u(1)+g_uF_v(1)$$ 所以还要同时转移一个 $h_u=F_u(1)$。于是得到线性的 DP： $$\begin{cases}g_u=\dfrac {Ny}{1-y}g_vg_u+g_vh_u+g_uh_v\\h_u=\dfrac {Ny}{1-y}g_vh_u+h_vh_u\end{cases}$$ **第三问** 即 $$\sum_{R}\text{cnt}^2(R\subseteq T)\cdot (\dfrac 1 y-1)^{|R|}$$ 和上面一样，容易得到它是 $$\dfrac{(\dfrac 1 y-1)^N}{N^4}\sum_{R}\prod \dfrac {N^2y}{1-y}a_i$$ 现在已经没有树可以让我们 DP 了…… 枚举一个 $a_i$ 序列，先假设点都无标号。 这时，其贡献是 $\prod \dfrac {N^2y}{1-y}a_i$，又有 $\prod a_i^{a_i-2}$ 个 $R$ 可以被其描述，总贡献是 $\prod \dfrac {N^2y}{1-y}a_i^{a_i}$。 称 $\dfrac{N^2y}{1-y}a_i^{a_i}=d(a_i)$。 但是点都有标号，即多个实际联通情况可以被其描述。下面进行分析。 设 $N$ 个点的第二问答案为 $ans_N$。枚举 1 号点所在联通块大小为 $j$。这种情况下的贡献是 $$\begin{pmatrix}N-1\\j-1\end{pmatrix}d(j)ans_{N-j}$$ 算了不用讲了，这个老早在本文开头就论证过了，即 $$ANS(x)=\text{Exp}\ D(x)$$ 草，终于推完了 总的来说找到方向就不难，除了开头的容斥和一个要猜的结论（也不难猜，而且手玩行列式也不难）之外都还是蛮自然的 ### **[P5400 [CTS2019]随机立方体](https://www.luogu.com.cn/problem/P5400)** 众所周知“恰好”这类词都必须被容斥掉（恰好：怎么天天迫害我）。所以转为统计 $f_i$：恰好有 $j$ 个极大点的方案会为它贡献 $\begin{pmatrix}j\\i\end{pmatrix}$。这样的技巧在 P5401 也用过。 二项式反演得： $ans=\dfrac{1}{(nml)!}\sum (-1)^{i-k}\begin{pmatrix}i\\k\end{pmatrix}f_i$。 好的，随便钦定 $i$ 个极大点，对于每个点都把它所在的三个平面（$x=x_p,y=y_p,z=z_p$）去掉：这些平面上不可能再有极大点。 至于剩下的点仍可能有极大点，反正我们不管了。事实上剩下的点怎么标号都没关系，影响不到我们的这 $i$ 个极大点。 答案即为： $$n^{\underline i}m^{\underline i}l^{\underline i}\begin{pmatrix}nml\\(n-i)(m-i)(l-i)\end{pmatrix}*\text{被去掉的点的排列数}$$ 剩下的 $nml-(n-i)(m-i)(l-i)$ 个点的情况要复杂一些，因为乱填的话可能使得原来钦定的 $i$ 个极大点不再极大。 $i$ 个极大点给每个去掉的坐标都下了限制。但是一个坐标最终只会被限制它的极大点的最小一个限制。所以每个极大点最终给几个坐标下了限制？ 显然，第 $j$ 小的极大点： $$(n-j+1)(m-j+1)(l-j+1)-(n-j)(m-j)(l-j)$$ 考虑第 $i$ 小的极大点：最大的极大点。它的值一定是能选的最大的一个，否则如果这个值填到别的地方，会使它自己或者别的极大点不极大。我们再选一些点填进被它限制的点。 考虑第 $i-1$ 小的极大点。它的值一定是剩下的最大的一个。 …… 于是，剩下的点的排列数为（记 $B(i)=(n-i)(m-i)(l-i)$） $$\prod_{j=1}^i \begin{pmatrix}B(0)-B(j)-1\\B(j-1)-B(j)-1\end{pmatrix}$$ 容易化成 $$(B(0)-B(i)-1)!\prod_{j=1}^{i-1}\dfrac{1}{B(0)-B(j)}$$ 好的，$f_i$ 即为 $$n^{\underline i}m^{\underline i}l^{\underline i}B(0)!\prod_{j=1}^{i}\dfrac{1}{B(0)-B(j)}$$ 于是 $$ans=\sum (-1)^{i-k}\begin{pmatrix}i\\k\end{pmatrix}n^{\underline i}m^{\underline i}l^{\underline i}\prod_{j=1}^i\dfrac{1}{B(0)-B(j)}$$ 前几个组合数都很好处理，现在时间复杂度瓶颈在于求 $B(0)-B(j)$ 的逆元。有一个 [trick](https://wa-am.com/2019/03/08/loj-%E4%B9%98%E6%B3%95%E9%80%86%E5%85%832-%E9%A2%98%E8%A7%A3/) 可以在 $O(N+\log p)$ 下离线求 $N$ 个数 $a_i$ 的逆元。于是这题就做完了。