UOJ#469. 【ZJOI2019】开关生成函数

亦凉 2023-08-17 16:21 134阅读 0赞

原文链接www.cnblogs.com/zhouzhendong/p/UOJ469.html

# 前言 #

clytql当场秒掉此题可惜不知道为什么fst了。

# 题解 #

考虑构建指数生成函数。

对于第 \$i\$ 项，设其概率为 \$p\_i\$ (即题目中的 \$p\_i / \\sum\_i p\_i\$) 。构建指数生成函数：

\\\[f\_i(x) = \\sum\_\{j\\geq 0, j\\bmod 2 = s\_i\} p\_i ^ j \\frac \{x^ j \} \{ j !\} \\\\ = \\frac 1 2 (e ^ \{p\_i x \} + (-1)^\{s\_i\} e ^ \{-p\_i x \})\\\]

\$F(x) = \\prod\_i f\_i(x) ,f(x) = \\sum\_\{i\} i! \[x^i\]F(x)\$ 的 \$k\$ 次项系数就是随机按 \$k\$ 次开关到达指定状态的概率。

我们要求的是第一次到达指定状态的概率，所以我们需要将多项式 \$f(x)\$ 除去"\$s\_i\$ 全为 0 时的多项式 \$g(x)\$"。

我们要算的是期望，所以我们要求的是

\\\[\\frac\{\\rm d\} \{ \{\\rm d\} x \} \\left ( \\frac \{f(x)\}\{g(x)\}\\right )\\\]

的各个系数之和。注意由于我们在求 \$f(x)\$、\$g(x)\$ 时，就已经乘了一个阶乘将指数生成函数转化成对应的普通生成函数了。因为我们要除去的方案是**从终止状态出发再回到终止状态的方案数**(OGF)，而不是**在到达终止状态之前绕一圈的方案数**(如果除以EGF)。

由于

\\\[\\cfrac\{\\rm d\} \{ \{\\rm d\} x \} \\left ( \\cfrac \{f(x)\}\{g(x)\} \\right ) = \\cfrac\{f'(x) g(x) - g'(x) f(x) \}\{g ^ 2(x)\}\\\]

于是，我们来对每一个项考虑一下：

\\\[ e ^ \{kx\} = \\sum\_\{i\\geq 0 \} k ^ i \\frac \{ x ^ i \} \{ i ! \} \\\]

\\\[\\sum\_\{i\\geq 0\} k ^ i x ^ i= \\frac\{1\}\{1 - kx\}\\\]

\\\[\\frac\{\\rm d\} \{ \{\\rm d\} x \} e ^ \{kx\} = k ^ 2 x e ^ \{kx\} = k ^ 2 x \\sum\_\{i\\geq 0 \} k ^ i \\frac \{ x ^ i \} \{ i ! \}\\\]

\\\[\\sum\_\{i\\geq 1\} k ^ \{i+1\} i \\cdot x ^ i = \\frac \{k\} \{ (1-kx) ^ 2\} \\\]

接下来我们把 \$x = 1\$ 代入求解。

考虑到当 \$k = 1\$ 时我们会得到 NAN，这导致了求解失败。

但是我们显然可以肯定答案不是 NAN。那么发生了什么？

之前提到，答案是

\\\[\\cfrac\{f'(x) g(x) - g'(x) f(x) \}\{g ^ 2(x)\}\\\]

我们只需要将分子分母上下同乘 \$(1-kx) ^ 2\$ 。

注意到 \$g^2(x)\$ 里面有 \$\\cfrac \{1\}\{(1-kx) ^ 2\}\$ ，但是 $f'(x) g(x) $ 和 \$f(x)g'(x)\$ 里面都有 \$\\cfrac \{1\}\{(1-kx) ^ 3\}\$ ，看起来似乎又是 NAN。注意到 $f'(x) g(x) $ 和 \$f(x)g'(x)\$ 里面的 \$\\cfrac \{1\}\{(1-kx) ^ 3\}\$ 项在减法时抵消了，所以没有影响。

总时间复杂度 \$O(n \\sum\{p\_ i\} )\$ 。

# 代码 #

#include <bits/stdc++.h> #define clr(x) memset(x,0,sizeof x) #define For(i,a,b) for (int i=(a);i<=(b);i++) #define Fod(i,b,a) for (int i=(b);i>=(a);i--) #define fi first #define se second #define pb(x) push_back(x) #define mp(x,y) make_pair(x,y) #define outval(x) cerr<<#x" = "<<x<<endl #define outtag(x) cerr<<"---------------"#x"---------------"<<endl #define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\ For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef vector <int> vi; LL read(){ LL x=0,f=0; char ch=getchar(); while (!isdigit(ch)) f|=ch=='-',ch=getchar(); while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return f?-x:x; } const int N=105,S=1e5+10,mod=998244353; int Pow(int x,int y){ int ans=1; for (;y;y>>=1,x=(LL)x*x%mod) if (y&1) ans=(LL)ans*x%mod; return ans; } void Add(int &x,int y){ if ((x+=y)>=mod) x-=mod; } void Del(int &x,int y){ if ((x-=y)<0) x+=mod; } int Add(int x){ return x>=mod?x-mod:x; } int Del(int x){ return x<0?x+mod:x; } int inv2=(mod+1)>>1; int n; int s[N],p[N],sum=0,invs; int f[S],g[S],val[S],inv[N],O=5e4+5; int ans=0; void Get(int *a){ static int b[S]; For(i,-sum,sum){ a[i+O]=0; val[i+O]=(LL)Del(i)*invs%mod; inv[i+O]=Pow(Del(1-val[i+O]),mod-2); } a[0+O]=1; For(i,1,n){ For(j,-sum,sum) b[j+O]=0; For(j,-sum,sum){ if (!a[j+O]) continue; Add(b[j+p[i]+O],a[j+O]); if (s[i]) Del(b[j-p[i]+O],a[j+O]); else Add(b[j-p[i]+O],a[j+O]); } For(j,-sum,sum) a[j+O]=b[j+O]; } } int calc1(int *a,int *b){ // a' * b * (1 - x) ^ 2 int ans=0; For(i,-sum,sum-1) Add(ans,(LL)b[i+O]*inv[i+O]%mod); ans=(LL)ans*a[sum+O]%mod; return ans; } int calc2(int *a){ return (LL)a[sum+O]*a[sum+O]%mod; } int main(){ n=read(); For(i,1,n) s[i]=read(); For(i,1,n) p[i]=read(),sum+=p[i]; invs=Pow(sum,mod-2); Get(f),clr(s),Get(g); Add(ans,calc1(f,g)); Del(ans,calc1(g,f)); ans=(LL)ans*Pow(calc2(g),mod-2)%mod; cout<<ans<<endl; return 0; }

转载于:https://www.cnblogs.com/zhouzhendong/p/UOJ469.html