题解：P13682 [IAMOI R2] 污水博弈
masterhuang
·
·
题解
官方题解不知所云，感觉挺不牛。
先给出一些结论：
g(n)=\sum\limits_{i=0}^{n}\dfrac{1}{i+2}\dbinom{n}{i}=\dfrac{n2^{n+1}+1}{(n+1)(n+2)}
\\
f(s)=\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m}\dfrac{1}{i+j+3}\dbinom{n}{i}\dbinom{m}{j}=\dfrac{(s^2+s+2)2^{s+1}-2}{(s+1)(s+2)(s+3)},s=n+m
大概证明思路就是利用 \dfrac{1}{k+1}={\displaystyle{\int}}_0^1 x^k\,\mathrm{d}x 然后二项式定理，最终分别计算
\int_0^1 x(x+1)^n\,\mathrm{d}x
\\
\int_0^1 x^2(x+1)^{n+m}\,\mathrm{d}x
就能得出结论。
- 所有开关方案总共 2^{n-1} 种，先计算总和再除 2^{n-1} 就是概率。
对于每个位置 w 单独算贡献，贡献 \times a_w 加到答案即可。
考虑 u=w-1,v=n-w，设包含 w 的区间往 [1,w-1] 扩展了 i 个数，往 [w+1,n] 扩展了 j 个数。
则贡献为 \sum\limits_{0\le i\le u,0\le j\le v}\dfrac{1}{i+j+1}F(u-i,v-j)
考虑包含 w 的区间左侧有 n 个数，右侧有 m 个数，此时左右随便切分，再随机选择一个区间。
则 F(n,m) 表示所有方案选到包含 w 的区间的概率和。
枚举左侧切分了 i 段，右侧 j 段：
F(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \dbinom{n-1}{i-1}\dbinom{m-1}{j-1}\dfrac{1}{i+j+1}=f(n+m-2)
但是要特判 n,m=0 的情况，不妨钦定 m=0。
- 若 n=m=0\Rightarrow F(0,0)=1
- 若 n\neq 0,m= 0,F(n,0)=\sum\limits_{i=1}^{n}\dbinom{n-1}{i-1}\dfrac{1}{i+1}=g(n-1)
我们注意到 F(n,m) 只和 [n=0]+[m=0] 和 n+m 相关。
考虑 [n=0]+[m=0]=t,n+m=s 的时候的贡献系数：
交换求和符号：
\begin{aligned}
ans&=\sum\limits_{w=1}^{n}a_w\sum\limits_{i\in [0,x-1],j\in [0,n-x]} \dfrac{1}{i+j+1}F(x-1-i,n-x-j)
\\
&=\sum\limits_{w=1}^{n}a_w\sum\limits_{i\in [0,x-1],j\in [0,n-x]} \dfrac{1}{n-i-j}F(i,j)
\\
&=\sum\limits_{i=0}^{n} c(0,i)f(i-2)+c(1,i)g(i-1)+c(2,i)
\end{aligned}
贡献系数 c 的计算方式如下：
c([i=0]+[j=0],i+j)\gets \dfrac{1}{n-i-j}a_w
\\
0\le i+j<n,i+1\le w\le n-j
特别的，越界的 f,g 统统看成 0。
发现可以最后再令 c(*,i)\gets c(*,i)\times \dfrac{1}{n-i}
前面只需要：
c([i=0]+[j=0],i+j)\gets a_w
\\
0\le i+j<n,i+1\le w\le n-j
此时答案为 \sum\limits_{i=0}^{n} \dfrac{1}{n-i}(c(0,i)f(i-2)+c(1,i)g(i-1)+c(2,i))
记 a 的前缀和为 s，s 的前缀和为 S。
考虑 c(2,*) 发现只有 c(2,0)=a_n。
考虑 c(1,*)，分别枚举 i=0 还是 j=0，发现 c(1,i)=s(n-i)+s(n)-s(i)。
否则统统是 c(0,*)，即：
c(0,i+j)\gets s_{n-j}-s_i
\\
i,j\ge 1,2\le i+j<n
于是 $c(0,s)=S(n-1)-S(n-i)-S(i-1)$。
算出系数，预处理出 $f,g$，于是就 $\mathcal{O}(n)$ 解决了这题。
- 不要忘记除 $2^{n-1}$ 哦！
**目前是最优最短解。**
::::info[$\bf{code}$]
```cpp
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e6+5,mod=998244353;
int n,a[N],I[N],s,p2[N],f[N],g[N],c[N];
inline int md(int x){return x>=mod?x-mod:x;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=1ll*s*x%mod),x=1ll*x*x%mod,p>>=1);return s;}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],a[i]=md(a[i-1]+a[i]);
I[1]=1;for(int i=2;i<=n;i++) I[i]=mod-1ll*I[mod%i]*(mod/i)%mod;
for(int i=*p2=1;i<=n;i++) p2[i]=md(p2[i-1]<<1);
for(int i=0;i<n-2;i++){
LL x=(1ll*i*(i+1)+2)%mod*p2[i]%mod;
f[i]=2*(x-1)*I[i+1]%mod*I[i+2]%mod*I[i+3]%mod;
}
for(int i=0;i<n-1;i++) g[i]=(1ll*i*p2[i+1]+1)%mod*I[i+1]%mod*I[i+2]%mod;
s=1ll*a[n]*I[n]%mod;
for(int i=1;i<n;i++) s=(s+((LL)a[n-i]+a[n]+mod-a[i])*I[n-i]%mod*g[i-1])%mod;
for(int i=1;i<=n;i++) a[i]=md(a[i]+a[i-1]);
for(int i=2;i<n;i++)
s=(s+((LL)mod-a[i-1]+a[n-1]+mod-a[n-i])*I[n-i]%mod*f[i-2])%mod;
cout<<1ll*s*ksm(2,mod-n)%mod;
return 0;
}
```
::::