时隔 \(9\)
个月，终于肝出这题了
设恰好有 \(i\) 条边不重复的方案数为 \(f_i\)
\[ f_i = \sum_{|E|=i}\sum_{E'\subseteq E}(-1)^{i-|E'|}n^{|E'|-1}\prod_{S=C(E')}s \] 交换求和次序得
\[ f_i = \sum_{E'}(-1)^{i-|E'|}n^{|E'|-1}\prod_{S=C(E')}s\sum_{|E|=i,E'\subseteq E} \]
化简得
\[ f_i = \sum_{E'}(-1)^{i-|E'|}n^{|E'|-1}\prod_{S=C(E')}s\binom{n-1-|E'|}{i-|E'|} \]
记
\[ \mathcal{F_i}=\sum_{|E|=i}\prod_{S=C(E)}s \]
则有
\[ f_i = \sum_{j=0}^i(-1)^{i-j}n^{j-1}\binom{n-1-j}{i-j}\mathcal{F_j} \]
答案为
\[ \sum_{i=0}^{n-1}\sum_{j=0}^i(-1)^{i-j}n^{j-1}\binom{n-1-j}{i-j}\mathcal{F_j}y^i \]
交换求和次序得
\[ \sum_{j=0}^{n-1}n^{j-1}\mathcal{F_j}\sum_{i=j}^{n-1}(-1)^{i-j}\binom{n-1-j}{i-j}y^{i+1} \]
化简为
\[ \sum_{j=0}^{n-1}n^{j-1}\mathcal{F_j}\sum_{i=0}^{n-1-j}y^{i+j+1}(-1)^{i}\binom{n-1-j}{i} \]
用二项式定理化简得
\[ \sum_{j=0}^{n-1}n^{j-1}y^{j+1}(1-y)^{n-1-j}\mathcal{F_j} \]
代入得
\[ \sum_{j=0}^{n-1}n^{j-1}y^{j+1}(1-y)^{n-1-j}\sum_{|E|=j}\prod_{S=C(E)}s \]
那么有
\[ \frac{(1-y)^n}{n^2}\sum_{j=0}^{n-1}n^{j+1}(\frac{y}{1-y})^{j+1}\sum_{|E|=j}\prod_{S=C(E)}s \]
进一步得
\[ \frac{(1-y)^{n}}{n^2}\sum_{E}\prod_{S=C(E)}\frac{ny}{1-y}s \]
后面部分可以使用背包完成，时间复杂度为 \(O(n^2)\)
设 \(f_n\) 为该联通块根节点所在联通块大小为 \(n\) 的方案数，\(k=\frac{1-y}{ny}\) 则在合并两个联通块时有
\[ h_n=k\sum_{i=0}^nf_ig_{n-i}(\frac{1}{i}+\frac{1}{n-i})+f_n\sum_{i=0}^Ng_i \]
注意到我们最后只需关注 \(\sum_{i=0}^Nf_i\) 并结合母函数的技巧启发我们考虑幂级数
\[ f(x)=\sum_{i=0}^Nf_ix^i \]
最后答案即为 \(f(1)\)
那么套在 DP 上就有
\[ \sum_{n=0}^Nh_nx^n=k\sum_{n=0}^N\sum_{i=0}^nf_ig_{n-i}(\frac{1}{i}+\frac{1}{n-i})x^n+\sum_{n=0}^Nf_n\sum_{i=0}^Ng_ix^n \]
化简为
\[ h(x)=k((\sum_{i=0}^n\frac{f_n}{n}x^n)g(x)+(\sum_{i=0}^n\frac{g_n}{n}x^n)f(x))+g(1)f(x) \]
考虑函数
\[ \hat{f}(x)=\sum_{i=0}^n\frac{f_i}{i}x^i \]
则有
\[ h(x)=k(\hat{f}(x)g(x)+\hat{g}(x)f(x))+f(x)g(1) \]
令 \(x=1\) 得到
\[ h(1)=k(\hat{f}(1)g(1)+\hat{g}(1)f(1))+f(1)g(1) \]
考虑 \(\hat{f}(x)\) 的求法
\[ \sum_{n=0}^N\frac{h_n}{n}x^n=k\sum_{n=0}^N\frac{1}{n}\sum_{i=0}^nf_ig_{n-i}(\frac{1}{i}+\frac{1}{n-i})x^n+\sum_{n=0}^N\frac{f_n}{n}\sum_{i=0}^Ng_ix^n \]
化简为
\[ \hat{h}(x)=k\hat{f}(x)\hat{g}(x)+\hat{f}(x)g(1) \]
同样
\[ \hat{h}(1)=k\hat{f}(1)\hat{g}(1)+\hat{f}(1)g(1) \]
这样我们就得到了 \(O(n)\) 的
DP
考虑 op3 的做法，答案为
\[ \sum_{T}\frac{(1-y)^{n}}{n^2}\sum_{E\subseteq T}\prod_{S=C(E)}\frac{ny}{1-y}s \]
用 prufer 序列枚举联通块得
\[ \frac{(1-y)^{n}}{n^4}\sum_{\sum_{i=1}^ms_i=n}\frac{1}{m!}\frac{n!}{\prod_{i=1}^ms_i!}\prod_{i=1}^ms_i^{s_i-2}\prod_{i=1}^m\frac{n^2y}{1-y}{s_i}^2 \]
考后面部分的 EGF 得，并设 \(w=\frac{n^2y}{1-y}\)
\[ [x^n]f=\sum_{\sum_{i=1}^ms_i=n}\frac{1}{m!}\prod_{i=1}^m\frac{ws_i^{s_i}}{s_i!} \]
这启发我们考虑函数 \(g=\sum_{i}w\frac{i^i}{i!}x^i\)
带入有
\[ f=\sum_m\frac{g^m}{m!} \]
用等比数列求和化简得
\[ f=e^g \]
最终答案即为
\[ \frac{n!(1-y)^{n}}{n^4}[x^n]f \]
1 |
|