首先对于需要按奇数次的开关,其生成函数为:
$$
F_i(x)=\sum_{n\,is\,odd}^{\infty}p_i^{n}\frac{x^{n}}{n!}
$$
然后对于需要按偶数次的开关,其生成函数为:
$$
F_i(x)=\sum_{n\,is\,even}^{\infty}p_i^{n}\frac{x^{n}}{n!}
$$

补充一下 $\rm{EGF}$ 的一些常用公式,首先最基础的:
$$
e^x=\sum_{n=0}^{\infty}\frac{x^n}{n!}=1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots+\frac{x^n}{n!}+\cdots\\
e^{-x}=\sum_{n=0}^{\infty}(-1)^{n}\frac{x^n}{n!}=1-\frac{x^1}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots+(-1)^n\frac{x^n}{n!}+\cdots\\
$$
根据上面两个公式可以得到:
$$
\sum_{n\,is\,odd}^{\infty}\frac{x^n}{n!}=\frac{x^1}{1!}+\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots+[n\text{ is odd}]\frac{x^n}{n!}+\cdots=\frac{e^x-e^{-x}}{2}\\
\sum_{n\,is\,even}^{\infty}\frac{x^n}{n!}=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}+[n\text{ is even}]\frac{x^n}{n!}+\cdots=\frac{e^x+e^{-x}}{2}\\
$$

上面的两个就可以简化了:
$$
F_i(x)=
\begin{cases}
\frac{e^{p_ix}-e^{-p_ix}}{2}\quad\text{if }i\text{ is odd}\\
\frac{e^{p_ix}+e^{-p_ix}}{2}\quad\text{if }i\text{ is even}\\
\end{cases}
$$
也可以写成:
$$
F_i(x)=\frac{e^{p_ix}+(-1)^{s_i}e^{-p_ix}}{2}
$$
然后令:
$$
\begin{aligned}
F(x)&=\prod_{i=1}^{n}F_i(x)\\
&=\prod_{i=1}^{n}\frac{e^{p_ix}+(-1)^{s_i}e^{-p_ix}}{2}\\
\end{aligned}
$$
假设遇到合法状态后还会继续按,对于按 $k$ 次开关才可以通过的概率为 $F(x)$ 的 $x^k$ 的系数。

令 $C(x)$ 的 $x^k$ 的系数表示按了 $k$ 次后,第一次出现合法状态的概率,令 $G(x)$ 的 $x^k$ 的系数表示一个状态再操作 $k$ 次后依旧是这个状态的概率。

根据 $G(x)$ 的定义,可以很简单的写出来 $G(x)$ 的式子:
$$
G(x)=\prod_{i=1}^{n}\frac{e^{p_ix}+e^{-p_ix}}{2}\\
$$
然后显然有 $C(x)G(x)=F(x)$,也就是 $C(x)=\frac{F(x)}{G(x)}$ 。

想一想答案是什么,对于权值为 $k$ ,其概率为 $C(x)$ 的 $x^k$ 的系数。

在这里令 $ans_k$ 表示 $C(x)$ 的 $x^k$ 的系数,那么答案为:
$$
ans=\sum_{i=0}^{\infty}i\cdot ans_i
$$
对于这个 $i$ ,对 $C(x)$ 求个导。求导的话,首先原来的 $x^0$ 会消失,但是本来我们就不关心 $x^0$ 的系数,因为权值是 $0$ ,对答案的贡献也就是 $0$ 。

至于求导后 $x^n$ 会变成 $nx^{n-1}$ 的话,因为这时我们并不关心某一项的系数,只关心总和,所以对于表示项数的 $x$ 直接忽略不管即可。

令 $x=1$ ,答案就是 $C'(1)$ 了:
$$
\begin{aligned}
C'(1)=\left(\frac{F(1)}{G(1)}\right)’
\end{aligned}
$$

补充一下怎么求一个函数除一个函数的导数,可以参考一下 维基百科
$$
\left(\frac{f(x)}{g(x)}\right)’=\frac{f'(x)g(x)-g'(x)f(x)}{[g(x)]^2}
$$
结论如上,证明如下:

令 $h(x)=\frac{f(x)}{g(x)}$ ,有 $f(x)=g(x)h(x)$ :
$$
f'(x)=g'(x)h(x)+g(x)h'(x)\\
$$
移项后:
$$
\begin{aligned}
h'(x)&=\frac{f'(x)-g'(x)h(x)}{g(x)}\\
&=\frac{f'(x)-g'(x)\frac{f(x)}{g(x)}}{g(x)}\\
&=\frac{f'(x)g(x)-g'(x)f(x)}{[g(x)]^2}\\
\end{aligned}
$$

于是现在我们就需要求这个玩意:
$$
\frac{F'(1)G(1)-G'(1)F(1)}{[G(1)]^2}
$$
回忆一下 $F,G$ :
$$
\begin{aligned}
F(x)&=\prod_{i=1}^{n}\frac{e^{p_ix}+(-1)^{s_i}e^{-p_ix}}{2}\\
G(x)&=\prod_{i=1}^{n}\frac{e^{p_ix}+e^{-p_ix}}{2}\\
\end{aligned}
$$
将 $x=1$ 带入:
$$
\begin{aligned}
F(1)&=\prod_{i=1}^{n}\frac{e^{p_i}+(-1)^{s_i}e^{-p_i}}{2}\\
G(1)&=\prod_{i=1}^{n}\frac{e^{p_i}+e^{-p_i}}{2}\\
\end{aligned}
$$
现在求的是 $\sum\limits_{i=0}^{\infty}p_i\frac{x^i}{i!}$ ,但是最终我们要求的是 $\sum\limits_{i=0}^{\infty}p_ix^i$ ,于是将 $F,G$ 转换为 $\rm{OGF}$ ,以 $F$ 为例。

对于 $e^{p_i}+(-1)^{s_i}e^{-p_i}$ 这个式子,显然可以表示为下述形式:
$$
\sum_{i=-\infty}^{\infty}a_ie^{ix}
$$
这个 $a_i$ 表示系数,除了 $i=p_i$ 和 $i=-p_i$ 两个地方,其他的 $a_i$ 都为 $0$ 。

然后现在将 $e^{p_i}+(-1)^{s_i}e^{-p_i}$ 和 $e^{p_j}+(-1)^{s_j}e^{-p_j}$ 相乘,容易发现乘出来的结果也符合上述形式。所以 $F,G$ 也可以表示为上述形式。

对于 $e^{cx}$ ,转成 $\rm{OGF}$ 也就是 $\frac{1}{1-cx}$ ,也就是这个形式:
$$
\sum_{i=-\infty}^{\infty}\frac{a_i}{1-ix}
$$
注意一下这里 $i$ 不是整数,并且可以被表示为 $\frac{k}{P}$ 的形式,其中 $P$ 是 $\sum p_i$ ,$k$ 是整数。

那么就有:
$$
\begin{aligned}
F(x)&=\sum_{i=-P}^{P}\frac{a_i}{1-\frac{i}{P}x}\\
G(x)&=\sum_{i=-P}^{P}\frac{b_i}{1-\frac{i}{P}x}\\
\frac{F(x)}{G(x)}&=\frac{\sum\limits_{i=-P}^{P}\frac{a_i}{1-\frac{i}{P}x}}{\sum\limits_{i=-P}^{P}\frac{b_i}{1-\frac{i}{P}x}}=\frac{\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)}{\sum\limits_{i=-P}^{P}b_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)}\\
\end{aligned}
$$
考虑令:
$$
A(x)=\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\\
B(x)=\sum\limits_{i=-P}^{P}b_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\\
$$
观察我们要求的东西:
$$
\frac{F'(1)G(1)-G'(1)F(1)}{[G(1)]^2}
$$
上下同时除一个数,答案是不会变的,所以答案其实是:
$$
\frac{A'(1)B(1)-A'(1)B(1)}{[B(1)]^2}
$$
最后一个问题,怎么求 $A'(x)$ 和 $B'(x)$ ?

补充一下怎么求一个函数乘一个函数的导数。
$$
(F(x)G(x))’=F'(x)G(x)+F(x)G'(x)
$$
扩展一下:
$$
\left(\prod_{i=1}^{n}F_i(x)\right)’=\prod_{i=1}^{n}F_i’(x)\left(\prod_{j=1,j\not=i}^{n}F_j(x)\right)
$$

为了方便,$i$ 将写成分数形式。( $P$ 的定义在上文已经给出) 。

那么可以得到:
$$
\begin{aligned}
A’(x)&=\left(\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\right)’\\
&=\sum\limits_{i=-P}^{P}\left(a_{\frac{i}{P}}\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\right)’\\
&=\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\left(\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)\right)’\\
&=\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\left(\prod\limits_{j=-P,j\not=i}^{P}(1-\frac{j}{P}x)’\left(\prod\limits_{k=-P,k\not=j,k\not=i}^{P}(1-\frac{k}{P}x)\right)\right)\\
&=\sum\limits_{i=-P}^{P}a_{\frac{i}{P}}\left(\prod\limits_{j=-P,j\not=i}^{P}(-\frac{j}{P})\left(\prod\limits_{k=-P,k\not=j,k\not=i}^{P}(1-\frac{k}{P}x)\right)\right)\\
\end{aligned}
$$
现在,带入 $x=1$ 。

至于为什么之前不能直接带入 $x=1$ ,是因为 $(A(1))’$ 不等价于 $A'(1)$ 。

(公式挂了插个图算了 /kel)

考虑令:
$$
S=\prod\limits_{k=-P}^{P-1}(1-\frac{k}{P})
$$
可以得到:
$$
A'(1)=a_1\left(\prod\limits_{j=-P}^{P-1}(-\frac{j}{P})\frac{S}{1-\frac{j}{P}}\right)-\sum_{i=-P}^{P-1}a_{\frac{i}{P}}\frac{S}{1-\frac{i}{P}}\\
$$
$B'(1)$ 的推导一模一样,现在计算 $A'(1)$ 和 $B'(1)$ 的时间复杂度是 $O(P)$ 的了 (可能带个逆元的 $\log$) 。

最后:
$$
A(1)=a_{1}\prod\limits_{j=-P}^{P-1}(1-\frac{j}{P})\\
B(1)=b_{1}\prod\limits_{j=-P}^{P-1}(1-\frac{j}{P})\\
A'(1)=a_1\left(\prod\limits_{j=-P}^{P-1}(-\frac{j}{P})\frac{S}{1-\frac{j}{P}}\right)-\sum_{i=-P}^{P-1}a_{\frac{i}{P}}\frac{S}{1-\frac{i}{P}}\\
B'(1)=b_1\left(\prod\limits_{j=-P}^{P-1}(-\frac{j}{P})\frac{S}{1-\frac{j}{P}}\right)-\sum_{i=-P}^{P-1}b_{\frac{i}{P}}\frac{S}{1-\frac{i}{P}}\\
$$
爆算这四个的时间复杂度是 $O(P)$ 的。

对于 $a,b$ ,直接背包爆算,时间复杂度是 $O(nP)$ 的。

Code:

int main() {
    #ifndef ONLINE_JUDGE
    freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    #endif

    IN(n);
    for(int i=1;i<=n;++i) IN(s[i]);
    for(int i=1;i<=n;++i) IN(p[i]),P+=p[i];
    invP=modpow(P,mod-2);

    memset(tmp,0,sizeof(tmp)),tmp[0][P]=1;
    for(int i=1;i<=n;++i) {
        int tag=(s[i]&1)?mod-1:1;
        for(int j=0;j<=P+P;++j) if(tmp[i-1][j]) {
            if(j+p[i]>=0&&j+p[i]<=P+P) pls(tmp[i][j+p[i]],tmp[i-1][j]);
            if(j-p[i]>=0&&j-p[i]<=P+P) pls(tmp[i][j-p[i]],mul(tag,tmp[i-1][j]));
        }
    }
    for(int i=0;i<=P+P;++i) a[i]=tmp[n][i];

    memset(tmp,0,sizeof(tmp)),tmp[0][P]=1;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=P+P;++j) if(tmp[i-1][j]) {
            if(j+p[i]>=0&&j+p[i]<=P+P) pls(tmp[i][j+p[i]],tmp[i-1][j]);
            if(j-p[i]>=0&&j-p[i]<=P+P) pls(tmp[i][j-p[i]],tmp[i-1][j]);
        }
    for(int i=0;i<=P+P;++i) b[i]=tmp[n][i];

    int A=a[P+P],B=b[P+P],T1=1,T2=1,S=1;
    for(int i=0;i<P+P;++i) A=mul(A,dec(1,mul(dec(i,P),invP)));
    for(int i=0;i<P+P;++i) B=mul(B,dec(1,mul(dec(i,P),invP)));
    for(int i=0;i<P+P;++i) S=mul(S,dec(1,mul(dec(i,P),invP)));
    for(int i=0;i<P+P;++i) T1=mul(T1,mod-mul(dec(i,P),invP));
    for(int i=0;i<P+P;++i) T2=mul(T2,mul(S,modpow(dec(1,mul(dec(i,P),invP)),mod-2)));

    int _A=mul(a[P+P],mul(T1,T2)),_B=mul(b[P+P],mul(T1,T2));
    for(int i=0;i<P+P;++i) sub(_A,mul(a[i],mul(S,modpow(dec(1,mul(dec(i,P),invP)),mod-2))));
    for(int i=0;i<P+P;++i) sub(_B,mul(b[i],mul(S,modpow(dec(1,mul(dec(i,P),invP)),mod-2))));

    int ans=mul(dec(mul(_A,B),mul(A,_B)),modpow(mul(B,B),mod-2));
    printf("%d\n",ans);
    return 0;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注