【loj3045】【ZJOI2019】开关

题目

$n$个开关，一开始处于关闭状态，你需要将他们按成$s$状态，按成了之后就停止操作;

每次按下开关的i概率为$\frac{p_i}{\sum_{i=1}^{n}p_i}$ ，问期望步数;

$1 \le n \le 100 \ , \ \sum_{i=1}^{n}p_i \le 5 \times 10^4 \ , \ p_i \ge 1$

题解

Part 1
设$F(x)$表示不停按$n$次最后到达 $ s $ 状态的 $ EGF $ ， $ G(x) $ 表示按了 $ n $ 次之后又回到原状态的 $ EGF $ , $ H(x) $ 表示答案的 $ EGF $ ，$ f(x),g(x),h(x) $ 是其分别对应的$OGF$

设 $P=\sum_{i=1}^{n}p_i$，考虑$e^x$和$e^{-x}$的展开构造得：

\[\begin{cases}
F(x) = \prod_{i=1}^{n} \frac{e^{\frac{p_i}{P}x} + (-1)^{s_i} e^{-\frac{p_i}{P} x }}{2} \\
G(x) = \prod_{i=1}^{n} \frac{e^{\frac{p_i}{P}x} + e^{-\frac{p_i}{P}x} }{2} \\
f = g * h \leftrightarrow h = \frac{f}{g}
\end{cases}
\\根据导数的定义，ans = h'(1) = \frac{f'(1)g(1)-f(1)g'(1)}{g^2(1)}
\]
Part 2
考虑求f(1)
$F(x)$和$G(x)$有共同的形式$F(x) = \sum_{i=-P}^{P}a_i e^{\frac{i}{P}x}$
同理设$G(x)$对应系数为$b_i$ ，下面只讨论F
首先$a_i$和$b_i$都可以通过简单的背包求得，然后：
$f(x) = OGF(F(x)) = \sum_{i=P}^{{-P}a_i\sum_{j=0}}{\infty} \frac{i^jxj}{P^j} = \sum_{i=-P}^{P} \frac{a_i}{1-\frac{i}{P}x } $
由于f(x)和g(x)在x=0处不收敛，所以同时乘以一个$\Pi_{i=1}^{n}(1-\frac{i}{P}x)$

\[f(x) = \sum_{i=-P}^{P}a_i \prod_{j \neq i} (1-\frac{j}{P}x) \to f(1) = a_P \prod_{i \neq P} (1-\frac{i}{P}x)
\]
Part 3
考虑求$f'(1)$
首先观察

\[(\prod_i(1+a_ix))' \ = \sum_{i} a_i \prod_{j \neq i} (1+a_jx)
\]
$f'(1)$分两步求：

\[\begin{cases}
\sum_{i\neq P} a_i \sum_{j \neq i}(-\frac{j}{P})\prod_{k \neq i,j} (1-\frac{k}{P}x)
\\= -\sum_{i \neq P} a_i \prod_{j \neq P,i}(1-\frac{j}{P}) &i \neq P \\
-a_P \sum_{i \neq P} \frac{i}{P} \prod_{j \neq P,i} (1-\frac{j}{P}x) \\
=-a_P \sum_{i \neq P} \frac{i}{P} \prod_{j \neq P,i} (1-\frac{j}{P}) &i=P \\
\end{cases}
\\即f'(1)= -\prod_{i \neq P}(1-\frac{i}{P}x) (\sum_{j \neq P} \frac{a_j}{1-\frac{j}{P}x}+ \frac{a_P}{P} \sum_{j\neq P} \frac{j}{1-\frac{j}{P}x} ) \\
\]
带入求解(注意到$a_p=b_p=\frac{1}{2^n}$，该约的约掉)得：

\[h'(1) = 2^n \sum_{i \neq P} \frac{b_i-a_i}{1-\frac{i}{P}x}
\]

背包求解即可，时间复杂度：$O(nP)$

#include<bits/stdc++.h>

#define ll long long

#define mod 998244353

using namespace std;

const int N=100010,ny2=(mod+1)>>1;

int n,s[N],p[N],f[N],g[N],tmp[N],P;

void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}

void upd(int*A,int x,int fg){

	for(int i=-P;i<=P;++i)tmp[i+P]=A[i+P],A[i+P]=0;

	int y1=ny2,y2=(mod+fg*ny2)%mod;

	for(int i=-P;i<=P;++i){

		if(i+x<=P)inc(A[i+x+P],(ll)tmp[i+P]*y1%mod);

		if(i-x>=-P)inc(A[i-x+P],(ll)tmp[i+P]*y2%mod);

	}

}

int pw(int x,int y){

	int re=1;

	while(y){

		if(y&1)re=(ll)re*x%mod;

		y>>=1;x=(ll)x*x%mod;

	}

	return re;

}

char gc(){

	static char*p1,*p2,ch[1000000];

	if(p1==p2)p2=(p1=ch)+fread(ch,1,1000000,stdin);

	return(p1==p2)?EOF:*p1++;

}

int rd(){

	int x=0;char c=gc();

	while(c<'0'||c>'9')c=gc();

	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();

	return x;

}

int main(){

//	freopen("switch.in","r",stdin);

	freopen("switch.out","w",stdout);

	n=rd();

	for(int i=1;i<=n;++i)s[i]=rd()?-1:1;

	for(int i=1;i<=n;++i)p[i]=rd(),P+=p[i];

	f[P]=g[P]=1;

	for(int i=1;i<=n;++i){

		upd(f,p[i],s[i]);

		upd(g,p[i],1);

	}

	int ans=0;

	for(int i=0;i<P<<1;++i)inc(ans,(ll)(mod-f[i]+g[i])*pw(2*P-i,mod-2)%mod);

	ans=(ll)ans*P%mod*pw(2,n)%mod;

	cout<<ans<<endl;

	return 0;

}

巴特西

【loj3045】【ZJOI2019】开关

题目

题解

最新文章

热门文章