Description
有一些一开始全都是关的开关，每次随机选择一个（每个开关概率不同）开关并改变它的状态，问达到目标状态的期望步数
Solution
\(P=\sum_{i=1}^{n}p_i\)
求出\(k\)步达到目标状态的概率的\(EGF\)
\[ F(x)=\prod_{i=1}^n\frac{e^{\frac{p_ix}{P}}+(-1)^{s_i}e^{-\frac{p_ix}{P}}}{2} \] 再求出\(k\)步回到原来的状态的概率的\(EGF\)\[ G(x)=\prod_{i=1}^n\frac{e^{\frac{p_ix}{P}}+e^{-\frac{p_ix}{P}}}{2} \] 对于上述函数，可以用背包求出\(F(x)=\sum_{i=-P}^P a_ie^{\frac{ix}{P}}\)中的系数\(a_i\)，\(G(x)\)的系数为\(b_i\)设\(k\)步到达且不多次到达目标状态的概率的\(EGF\)为\(H(x)\)
设\(H(x),F(x),G(x)\)对应的\(OGF\)分别是\(h(x),f(x),g(x)\)
那么可知\(g(x)h(x)=f(x)\)
如何实现\(EGF\)到\(OGF\)的转化？
\[ \begin{equation} \begin{split} F(x)&=\sum_{i=-P}^Pa_ie^{\frac{ix}{P}} \\&=\sum_{i=-P}^P a_i\sum_{j\geq0}\frac{(\frac{ix}{P})^j}{j!} \end{split} \end{equation} \] 所以\[ f(x)=\sum_{i=-P}^P\frac{a_i}{1-\frac{ix}{P}} \] 发现我们要求的答案就是\(h'(1)\)\[ h'(1)=(\frac{f(1)}{g(1)})'=\frac{f'(1)g(1)-f(1)g'(1)}{g^2(1)} \] 计算时，把\(f,g\)同乘上\(\prod_{i=_P}^P(1-\frac{ix}{P})\)。下述\(f,g\)均已乘上左式。计算得到：
\[ f(1)=a_P\prod_{i=-P}^{P-1}(1-\frac{i}{P}) \\g(1)=b_P\prod_{i=-P}^{P-1}(1-\frac{i}{P}) \] 求导得到：\[ f'(1)=\sum_ia_i\sum_{j\neq i}-\frac{j}{P}\prod_{k\neq i,k\neq j}(1-\frac{k}{P})\\g'(1)=\sum_ib_i\sum_{j\neq i}-\frac{j}{P}\prod_{k\neq i,k\neq j}(1-\frac{k}{P}) \] 整理得到：\[ f'(1)=-(\sum_{i\neq P}\frac{a_i+a_P\cdot \frac{i}{P}}{1-\frac{i}{P}})(\prod_{i \neq P} (1-\frac{i}{P})) \\ g'(1)=-(\sum_{i\neq P}\frac{b_i+b_P\cdot \frac{i}{P}}{1-\frac{i}{P}})(\prod_{i \neq P} (1-\frac{i}{P})) \] 直接代入\(a_P=b_P=2^{-n}\)，最后答案为\(2^n\sum_{i\neq P}\frac{b_i-a_i}{1-\frac{i}{P}}\)
Code
#include#define ll long longusing namespace std;#define reg registerinline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f;}const int MX=5e4+5,M=998244353,inv2=(M+1)>>1;int Mul(int x,int y){return (1ll*x*y)%M;}int Add(int x,int y){return (x+y)%M;}int fpow(int x,int y=M-2){int r=1;for(;y;y>>=1,x=Mul(x,x))if(y&1)r=Mul(r,x);return r;}int n,a[MX<<1],b[MX<<1],s[105],p[105],P=0;int f[2][MX<<1],g[2][MX<<1];int _(int x){return x+P;}int main(){ n=read();register int i,j,k; for(i=1;i<=n;++i) s[i]=read(); for(i=1;i<=n;++i) p[i]=read(),P+=p[i]; f[0][P]=g[0][P]=1; for(k=0,i=1;i<=n;k+=p[i],++i) { memset(f[i&1],0,sizeof f[i&1]); memset(g[i&1],0,sizeof g[i&1]); for(j=-k;j<=k;++j) f[i&1][_(j+p[i])]=Add(f[i&1][_(j+p[i])],Mul(f[(i&1)^1][_(j)],inv2)), f[i&1][_(j-p[i])]=Add(f[i&1][_(j-p[i])],Mul(f[(i&1)^1][_(j)],s[i]?M-inv2:inv2)), g[i&1][_(j+p[i])]=Add(g[i&1][_(j+p[i])],Mul(g[(i&1)^1][_(j)],inv2)), g[i&1][_(j-p[i])]=Add(g[i&1][_(j-p[i])],Mul(g[(i&1)^1][_(j)],inv2)); } int ans=0,invP=fpow(P); for(i=-P;i
Blog来自PaperCloud，未经允许，请勿转载，TKS！