题意：有
个开关，每个开关有
两种状态，初始状态为 。
对某个开关进行操作可以使得其状态改变，由 变为 或由 变为 。
每个开关都有目标状态，记
为第
个开关的目标状态，当所有开关都达到目标状态，任务达成。
操作按照一定规则随机，具体地，第 个开关有权值 ，随机到的概率即为 。
求按上述规则随机操作时，完成任务所需的期望操作次数。
答案对 取模，，，时限 。
题目中“一达成目标就停止”的要求是经典的，考虑 PGF。
设 为在
次操作后达成目标的概率，对应的概率生成函数为 。
设 为在
次操作后回到原状态的概率，对应的概率生成函数为 。
设 为在
次操作后第一次达成目标的概率，对应的概率生成函数为 。
只有 才是一个标准的
PGF，满足 ，而 也正是答案。
根据 xor 的良好性质，对于一种在第
步达成目标的情况，肯定是之前某处（或这一步）已经达成过，然后经过若干步又回到达成状态，故
于是，我们只需设法得到 。
记 。
将我们每一轮按下的开关写成一个序列，称作“操作序列”。
记 表示操作序列中 出现的次数，当 时，开关 此时在目标状态。
于是，对开关 构造 EGF
计算 ， 即为在
次操作后达成目标的概率。
设 为用
次操作回到原状态的概率，等价于所有 时的 。
不难写出
但此处是 EGF，需要转化为 OGF。考虑将
作为基本单位，最后将其线性组合转化为 OGF。（类似于对 OGF
的分式分解）
具体地， 被转化为 ，它们对应的数列都是 。
将某 EGF 表示为 的形式，其中
是系数。
由于本题的特殊性，
均可以这样表示，且 的值只有较少的
个。
暴力卷积即可 地求出
的表示，即
然后将其转为系数对应的 OGF。
于是我们只需求出 。
的系数是等比数列
，其系数和即为
。
但这只在
时成立，我们的表示中存在着不收敛的 项，故要预先乘以 以避免这种情况。
于是我们只需求出 。
显然有 。
的系数对应数列 ，系数和为
由此不难求出 。