您的位置: 首页  >  IT文章  >  【loj3045】【ZJOI2019】开关

【loj3045】【ZJOI2019】开关

分类: IT文章 • 2023-03-29 11:54:22

题目

(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 imes 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})的展开构造得：

    [egin{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_isum_{j=0}^{infty} frac{i^jx^j}{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 eq i} (1-frac{j}{P}x) o f(1) = a_P prod_{i eq P} (1-frac{i}{P}x) ]

  • Part 3

  • 考虑求(f'(1))

  • 首先观察

    [(prod_i(1+a_ix))' = sum_{i} a_i prod_{j eq i} (1+a_jx) ]

  • (f'(1))分两步求：

    [egin{cases} sum_{i eq P} a_i sum_{j eq i}(-frac{j}{P})prod_{k eq i,j} (1-frac{k}{P}x) \= -sum_{i eq P} a_i prod_{j eq P,i}(1-frac{j}{P}) &i eq P \ -a_P sum_{i eq P} frac{i}{P} prod_{j eq P,i} (1-frac{j}{P}x) \ =-a_P sum_{i eq P} frac{i}{P} prod_{j eq P,i} (1-frac{j}{P}) &i=P \ end{cases} \即f'(1)= -prod_{i eq P}(1-frac{i}{P}x) (sum_{j eq P} frac{a_j}{1-frac{j}{P}x}+ frac{a_P}{P} sum_{j eq P} frac{j}{1-frac{j}{P}x} ) \ ]

  • 带入求解(注意到(a_p=b_p=frac{1}{2^n})，该约的约掉)得：

    [h'(1) = 2^n sum_{i eq 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;
}

相关推荐