题解：P13682 [IAMOI R2] 污水博弈
Tom17
·
·
题解
非常可以的计数题。
对式子的推导
思考怎么来算比较方便。直接枚举区间 l 和 r 没什么前途。我们考虑枚举每一个位置，计算其值在所有区间的贡献。
我们这样来算：先确定位置 x，然后确定其所在区间的长度，然后确定其区间的左边区间和右边区间的数量 cnt 。如下：
\sum_{x=1}^n\sum_{d=1}^n\sum_{l\le x\land l+d-1\ge x}\frac{a_x}{d}\sum_{cnt=0}^{n-d}\frac 1 {cnt+1}\sum_{cnt_l=0}^{cnt_l}\binom{l-2}{cnt_l-1}\binom{n-r-1}{cnt-cnt_l-1}
其中，l 是区间的左端点，假定我们枚举没有超出边界的区间。cnt_l 是左边区间的数量。组合数枚举区间中隔板的选择情况。
上述式子中会出现组合数下指数为 -1 的情况，这是对应左/右区间不存在（l=1 或 r=n）的情况，此时必须不选区间，即上指数也为 -1。如果左/右区间存在，则不能不选。所以额外定义：
\binom{k}{-1}=
\begin{cases}
1 & k=-1\\
0 & k\ge 0
\end{cases}
对式子交换求和符号：
\sum_{d=1}^n
\frac 1 d
\sum_{x=1}^n
\sum_{l\le x\land l+d-1\ge x}a_x
\sum_{cnt=0}^{n-d}\frac 1 {cnt+1}
\sum_{cnt_l=0}^{cnt_l}\binom{l-2}{cnt_l-1}\binom{n-r-1}{cnt-cnt_l-1}
当 l\ge 2 且 r\le n-1 时，后面这部分可以直接使用范德蒙德卷积。当 l=1 或者 r=n 时，由于上指数为 -1，范德蒙德卷积会出错，所以分开讨论。
更进一步，当讨论 l=1 或 r=n 时，l=1\land r=n 会被另外讨论，因为其同样会使此处上指数为 -1。
所以将区间分开以下三种情况讨论：
-
-
-
第一种（l\ge 2 且 r\le n-1）
原式为
\sum_{d=1}^{n-2}
\frac 1 d
\sum_{x=1}^n
\sum_{2\le l\le x\land x \le l+d-1 \le n-1}a_x
\sum_{cnt=0}^{n-d}\frac 1 {cnt+1}
\sum_{cnt_l=0}^{cnt_l}\binom{l-2}{cnt_l-1}\binom{n-r-1}{cnt-cnt_l-1}
记
b(d)=\sum_{x=1}^n\sum_{2\le l\le x\land x \le l+d-1 \le n-1}a_x
\begin{aligned}
h(D)&=\sum_{cnt=2}^{D+2}\frac 1 {cnt+1} \binom{D}{cnt-2},D\ge 2\\
&=\sum_{cnt=0}^{D}\frac 1 {cnt+3} \binom{D}{cnt},D\ge 2
\end{aligned}
（b 算贡献，h 算方案。）
对后面式子使用范德蒙德卷积后，式子为
\sum_{d=1}^{n-2}
\frac 1 d\times
b(d)\times h(n-d-2)
考虑 b(d) 的计算，将每一个 a_x 的系数写出来，不难发现递推规律：
b(1)=z_{n-1}-z_{2}\\
b(d)=b(d-1)+z_{n-d}-z_{d+1},d\ge 2
（其中z_x 为 a_x 的前缀和数组。）
### 第二种（$l=1$ 且 $r<n$ 或 $l>1$ 且 $r=n$）
设 $g(D)$ 为
$$
\begin{aligned}
g(D)&=\sum_{cnt=1}^{D+1}\frac 1 {cnt+1} \binom{D}{cnt-1}\\
&=\sum_{cnt=0}^{D}\frac 1 {cnt+2} \binom{D}{cnt}
\end{aligned}
$$
（其中 $D\ge 2$。）
类似上面的套路推一推，可以如下式子。
$l=1$ 时，贡献为
$$\sum_{d=1}^{n-1}g(n-d-1)\times\frac 1 d \times z_d$$
$r=n$ 时，贡献为
$$\sum_{d=1}^{n-1}g(n-d-1)\times\frac 1 d \times (z_n-z_{n-d})$$
（其中$z_x$ 为 $a_x$ 的前缀和数组。）
$g(D)$ 的推导也先放一放。
### 第三种 （$l=1$ 且 $r=n$）
显然为
$$\frac {z_n} n$$
## 关于 $g(D)$，$h(D)$ 的推导
发现我们是在计算这样的东西：（$k=1,2,3,\cdots$）
$$
\sum_{cnt=0}^{D}\frac 1 {cnt+k} \binom{D}{cnt}
$$
把组合数拆开，发现当 $k=1$ 时，$cnt+1$ 刚好可以乘入分母中。将分子先乘上一个 $D+1$ 后，就变为 $D+1$ 该行的组合数。
由于 $x$ 行的组合数之和为 $2^x$，并且计算时缺少了 $D+1$ 行的最后一项，所以和为 $2^{D+1}-1$。最后再除以回 $D+1$。
所以
$$
\sum_{cnt=0}^{D}\frac 1 {cnt+1} \binom{D}{cnt}=\frac{2^{D+1}-1}{D+1}
$$
设
$$
\begin{aligned}
f(D)&=\sum_{cnt=0}^{D}\frac 1 {cnt+1} \binom{D}{cnt}
\end{aligned}
$$
考虑扩展到 $k\ge 2$ 的情况。
组合数推导式和其对称性，造就了其可以差分的性质。
对于一个 $x$，将 $x$ 行的组合数每个分别减去其 $x-1$ 行同一列的组合数，得到的是 $x-1$ 行组合数向右平移一个位置的序列。
发现此时系数刚好会向右平移 $1$ 格。
$k=2$ 时，可以得到
$$g(D)=f(D+1)-f(D)$$
$k=3$ 时，同理可以得到
$$h(D)=g(D+1)-g(D)$$
（证明直接错位相减即可。）
### End
把三种结果加起来，乘上总方案数的倒数（为 $\frac 1 {2^{n-1}}$），即为最终结果。
ps: 如果上述式子有错误，还请读者批评指出。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1000050,mod=998244353;
#define rep(i,s,t) for(int i=s;i<=t;++i)
#define per(i,t,s) for(int i=t;i>=s;--i)
typedef long long LL;
int quick_pow(int a,int p)
{
if(p==0) return 1;
int c=quick_pow(a,p>>1);
c=(LL)c*c%mod;
if(p&1) c=(LL)c*a%mod;
return c;
}
int inc(int x)
{
return x>=mod ? x-mod : x;
}
int n,arr[N],jiec[N],invj[N],invn[N],qianz[N],f[N],g[N],h[N];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
rep(i,1,n)
{
cin>>arr[i];
}
rep(i,1,n) qianz[i]=inc(qianz[i-1]+arr[i]);
jiec[0]=invj[0]=1;
rep(i,1,n+10)
{
jiec[i]=(LL)jiec[i-1]*i%mod;
}
invj[n+10]=quick_pow(jiec[n+10],mod-2);
per(i,n+9,1)
{
invj[i]=(LL)invj[i+1]*(i+1)%mod;
}
rep(i,1,n+10)
{
invn[i]=(LL)invj[i]*jiec[i-1]%mod;
}
int P=1;
rep(i,0,n+2)
{
P=inc(P*2);
f[i]=(LL)(P-1)*invn[i+1]%mod;
}
rep(i,0,n+1)
{
g[i]=inc(f[i+1]-f[i]+mod);
}
rep(i,0,n)
{
h[i]=inc(g[i+1]-g[i]+mod);
}
int ans1=0;
P=0;
rep(i,1,n-2)
{
P=inc(P+qianz[n-i]);
P=inc(P-qianz[i]+mod);
ans1=inc(ans1+(LL)h[n-i-2]*invn[i]%mod*P%mod);
}
int ans2=0;
rep(i,1,n-1)
{
ans2=inc(ans2+(LL)g[n-i-1]*invn[i]%mod*inc((qianz[i])+inc(qianz[n]-qianz[n-i]+mod))%mod);
}
int ans3=(LL)qianz[n]*invn[n]%mod;
cout<<((LL)ans1+ans2+ans3)%mod*quick_pow(quick_pow(2,n-1),mod-2)%mod<<'\n';
return 0;
}
```