【2019北京集训测试赛(七)】 操作 分治+FFT+生成函数

题目大意:你有$n$个操作和一个初始为$0$的变量$x$。

第$i$个操作为:以$P_i$的概率给$x$加上$A_i$,剩下$1-P_i$的概率给$x$乘上$B_i$。

你袭击生成了一个长度为$n$的排列$C$,并以此执行了第$C_1,C_2....C_n$个操作。

求执行完所有操作后,变量$x$的期望膜$998244353$的值。

数据范围:$n≤10^5,0≤P,A,B<998244353$

我太菜了

考虑如果并没有排列的要求,而是强行依次执行,会发生什么事情:

令$X_i$表示执行完前$i$个操作后$x$的期望。

则有:

$X_i=P_i\times (X_{i-1}+A_i)+(1-P_i)\times X_{i-1}\times B_i$

我们经过化简,得到:

$X_i=(P_i+B_i-P_i\times B_i)X_{i-1}+A_i\times B_i$

这个不就是一个一次函数吗?我们姑且将这个称为$F_i(x)$,我们将它表示为$F_i(x)=D_ix+E_i$

那么在不考虑顺序的情况下,则有:

$X_n=F_1(F_2(...F_n(0)...))$

然而求答案的时候,函数排列的顺序是随机的,对于任意的$i≠j$,函数i排在函数j前面的概率都是$\frac{1}{2}$。

我们只需要求出,对于每个$E_i$,套在$F_i(x)$外面的函数的积的期望。

基于这些,则有:

$X_n=\frac{1}{n!}\sum \limits_{i=1}^{n} E_i \sum \limits_{j=1}^{n} [x^j] \prod \limits_{k=1,k\not\equiv i}^{n}(1+D_k)$

然后,我们通过分治FFT求解这个式子即可。

 #include<bits/stdc++.h>
#define MOD 998244353
#define G 3
#define L long long
#define M 262144
using namespace std; L pow_mod(L x,L k){L ans=; for(;k;k>>=,x=x*x%MOD) if(k&) ans=ans*x%MOD; return ans;}
void chage(int a[],int n){
for(int i=,j=;i<n-;i++){
if(i<j) swap(a[i],a[j]);
int k=n>>;
while(j>=k) j-=k,k>>=;
j+=k;
}
}
inline int pls(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}
inline int mns(int a,int b){return a<b?a-b+MOD:a-b;}
void NTT(int a[],int n,int on){
chage(a,n);
for(int h=;h<=n;h<<=){
int wn=pow_mod(G,(MOD-)/h);
for(int j=;j<n;j+=h){
int w=;
for(int k=j;k<j+(h>>);k++){
int u=a[k],t=1LL*a[k+(h>>)]*w%MOD;
//a[k]=(u+t)%MOD; a[k+(h>>1)]=(u-t+MOD)%MOD;
a[k]=pls(u,t); a[k+(h>>)]=mns(u,t);
w=1LL*w*wn%MOD;
}
}
}
if(on==-){
L inv=pow_mod(n,MOD-);
reverse(a+,a+n);
for(int i=;i<n;i++) a[i]=1LL*a[i]*inv%MOD;
}
}
void MUL(int ans[],int a[],int lena,int b[],int lenb){
static int t1[M],t2[M];
int len=; while(len<=lena+lenb) len<<=;
memset(t1,,len<<); memcpy(t1,a,(lena+)<<);
memset(t2,,len<<); memcpy(t2,b,(lenb+)<<);
NTT(t1,len,); NTT(t2,len,);
for(int i=;i<len;i++) t1[i]=1LL*t1[i]*t2[i]%MOD;
NTT(t1,len,-);
memcpy(ans,t1,(lena+lenb+)<<);
} L D[M]={},E[M]={},fac[M]={};
void solve(int f[],int g[],int l,int r){
static int h[M];
if(l==r) return f[]=E[l],g[]=D[l],g[]=,void();
int mid=(l+r)>>,lenl=mid-l+,lenr=r-mid;
solve(f,g,l,mid); solve(f+lenl+,g+lenl+,mid+,r);
MUL(h,f,lenl-,g+lenl+,lenr);
MUL(f,f+lenl+,lenr-,g,lenl);
for(int i=;i<=r-l+;i++) f[i]=(f[i]+h[i])%MOD;
MUL(g,g,lenl,g+lenl+,lenr);
} int ff[M]={},gg[M]={};
int main(){
fac[]=; for(int i=;i<M;i++) fac[i]=fac[i-]*i%MOD;
int n; scanf("%d",&n);
for(int i=;i<=n;i++){
L P,B,A; scanf("%lld%lld%lld",&P,&A,&B);
D[i]=(P+B-P*B%MOD+MOD)%MOD;
E[i]=A*P%MOD;
}
solve(ff,gg,,n);
L ans=;
for(int i=;i<n;i++) (ans+=1LL*ff[i]*fac[i]%MOD*fac[n-i-])%=MOD;
ans=ans*pow_mod(fac[n],MOD-)%MOD;
cout<<ans<<endl;
}
上一篇:AngularJS中的控制器示例


下一篇:[原]Jenkins(八)---jenkins构建项目报错时发送错误报告邮件