题目链接:[https://codeforces.com/gym/104053/problem/I]
有很简单的背包做法,但是本人赛后想了很久一些关于 \(\times 0\) 怎么求逆之类的(无聊问题),本文主要讨论了一下基于生成函数的卷积
以下设初始得病的概率是 \(\alpha_u\),被相邻的点感染的概率是 \(p_u\)
考虑假设初始的时候哪个点被感染是确定的,设 \(u\) 的生成函数为 \(F_u(x)\),\([x^k]\) 表示 \(u\) 的子树中感染了 \(k\) 个点的概率
我们考虑转移 \(F_u(x) = (p_ux \times \prod_{v \in son(u)} F_v(x)) + (1 – p_u)\)
显然结果是一个关于 \(n\) 的多项式
但如果我们依次枚举哪个点初始时被感染,时间复杂度将达到难以接受的 \(O(n^3)\),一个比较显然的想法是考虑换根 dp ,然而这些多项式并不一定有逆(可能常数项为 0 )
不过当然有一些神奇的维护前缀后缀的方法,此处暂时不说
我们考虑多一个占位符 \(y\),来表示是否存在初始时被感染的点,那么 \([y]\) 的结果(一个 \(n\)次多项式即我们想要的答案)
考虑构造一个二元的多项式环 \((\Z(x,y)\bmod y^2)\)
那么转移变成了 \(F_u(x,y) = ((p_u x + \alpha_u xy) \times \prod_{v \in son(u)}F_v(x)) + (1 – p_u)\)
考虑最后的结果为 \(y * P_1(x) + P_2(x)\),并注意到我们只关心 \(P_1(x)\),并且 \(P_1(x)\)是一个至多 n 次多项式
考虑枚举 \(x = \{1,2,3,4,….n,n+1\}\),转移的时候就只相当于在一个 \((\bmod y^2)\) 的一元多项式环上做乘法,这一步是 \(O(n^2)\)
然后,我们可以得到一个 \(P_1(x)\) 的点值表示,插值把系数插出来即可,这一步也是 \(O(n^2)\)
\(ans_k\) 即 \(P_1(x)[x^k] = F_{rt}(x,y)[x^k][y^1]\)
原文地址：http://www.cnblogs.com/y-dove/p/16899755.html
