原文链接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;

}

巴特西

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

前言

题解

代码

最新文章

热门文章

巴特西

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

前言

题解

代码

最新文章

热门文章

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