- 有(n)个开关，每个开关有一个权值(p_i)。
- 每轮操作会以(frac{p_i}{sum_{i=1}^{n}p_i})的概率选中一个开关改变它的状态。
- 给定目标状态(s_i)，问达到该状态的期望轮数。
- (nle100,sum p_ile5 imes10^4)
发现生成函数什么的果然还是啥也不会。。。
看来与去年相比，在这方面上唯一的进步就是能看懂题解了。。。
指数型生成函数
首先，方便起见令(P=sum_{i=1}^np_i)。
考虑对于一个目标状态(s_i=0)的位置，相当于要选中这个开关偶数次，而对于(s_i=1)的位置就是要选中奇数次。
也就是说，第(i)个位置的指数型生成函数就是：
那么总生成函数应该就是(F_1(x)*F_2(x)*F_3(x)*...*F_n(x))，也就是：
考虑这个函数的实际意义，它对应的普通生成函数的(i)次项系数表示的是(i)轮操作之后能得到目标状态的概率。
但我们要求的是它第一次到达目标状态的期望轮数，而如果仅仅通过(F(x))这一个函数计算答案，到达一次目标状态之后我们依然会统计到它的贡献！
因此我们还要构造一个函数(G(x))，让它的(i)次项系数表示(i)轮操作之后所有开关状态不变的概率。把这和(F(x))一对比，发现(G(x))其实就是(s_i)全等于(0)的(F(x))，二者的求法应该是完全一致的（具体的求法之后会介绍）。
那么，我们最终的生成函数就应该是(H(x)=frac{F(x)}{G(x)})。
然后我们先考虑最终答案的表示，应该是：
这形式看起来非常眼熟，仔细一想发现实际上这就是(H'(1))。
再次提醒，最终的(F(x),G(x),H(x))都应该是普通生成函数。
背包求解生成函数系数
现在，我们来考虑如何求出(F(x))的系数。
显然这玩意儿是一个无限函数，不可能说求出它每一项的系数。
故考虑先把(F(x))表示成(sum_ia_ie^{frac{i}{P}x})的形式。观察之前的式子容易发现，最终的(i)取值范围应该是([-P,P])。
既然(n,P)的范围都比较小，我们可以直接(O(nP))暴力背包来求出(a_i)这个数组。
众所周知(e^{frac ipx})的第(k)次项系数为((frac ip)^k)。
因为我们最终需要的是普通生成函数，所以把(F(x))转化成(OGF)得到：
同理我们求出(G(x))的数组(b_i)，得到：
最终的答案计算
考虑(H'=(frac FG)')，而根据除法求导法则有((frac FG)'=frac{F'G-G'F}{G^2})，因此：
但是，我们发现(F,F',G,G')四个函数在(x=1)的时候都不收敛，没办法直接求出(F(1),F'(1),G(1),G'(1))。
不过，由于我们要求的是((frac FG)')，如果给(F)和(G)都乘上同一个多项式(1-x)，式子的结果并不会改变。
而这样一来，就会发现我们要求的东西都变得非常简单了，实际上此时就有：（这应该非常显然）
那么答案就是：
化简一下得到：
具体实现还是非常简单的。
代码：(O(nsum p))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100
#define SZ 50000
#define X 998244353
#define I2 499122177
using namespace std;
int n,s[N+5],P,p[N+5],a[2*SZ+5],b[2*SZ+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int tmp[2*SZ+5];I void DP(int* f)//背包求解多项式系数
{
f[P]=1;for(RI i=1,j;i<=n;++i)//枚举每个位置
{
for(j=0;j<=2*P;++j) tmp[j]=f[j],f[j]=0;//备份当前数组
for(j=0;j+p[i]<=(P<<1);++j) f[j+p[i]]=(1LL*I2*tmp[j]+f[j+p[i]])%X;//第一种转移
for(j=p[i];j<=(P<<1);++j) f[j-p[i]]=(1LL*(s[i]?X-1:1)*I2%X*tmp[j]+f[j-p[i]])%X;//第二种转移
}
}
int main()
{
RI i;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d",s+i);for(i=1;i<=n;++i) scanf("%d",p+i),P+=p[i];
RI t=0,ipt=QP(P,X-2);for(DP(a),memset(s,0,sizeof(s)),DP(b),i=-P;i^P;++i)//两次背包求出两个多项式系数
t=((1LL*a[i+P]*b[P<<1]-1LL*a[P<<1]*b[i+P]%X+X)%X*QP((1LL*(i+X)*ipt-1)%X,X-2)+t)%X;//统计答案
return printf("%d
",1LL*QP(b[P<<1],X-3)*t%X),0;
}