专栏文章

题解：P13682 [IAMOI R2] 污水博弈

TTom17
P13682题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mioerfmd
此快照首次捕获于
2025/12/02 18:01
3 个月前
此快照最后确认于
2025/12/02 18:01
3 个月前
查看原文
非常可以的计数题。

对式子的推导

思考怎么来算比较方便。直接枚举区间 ll 和 rr 没什么前途。我们考虑枚举每一个位置，计算其值在所有区间的贡献。
我们这样来算：先确定位置 xx，然后确定其所在区间的长度，然后确定其区间的左边区间和右边区间的数量 cntcnt 。如下：
∑x=1n∑d=1n∑l≤x∧l+d−1≥xaxd∑cnt=0n−d1cnt+1∑cntl=0cntl(l−2cntl−1)(n−r−1cnt−cntl−1)\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}
其中，ll 是区间的左端点，假定我们枚举没有超出边界的区间。cntlcnt_l 是左边区间的数量。组合数枚举区间中隔板的选择情况。
上述式子中会出现组合数下指数为 −1-1 的情况，这是对应左/右区间不存在（l=1l=1 或 r=nr=n）的情况，此时必须不选区间，即上指数也为 −1-1。如果左/右区间存在，则不能不选。所以额外定义：
(k−1)={1k=−10k≥0\binom{k}{-1}= \begin{cases} 1 & k=-1\\ 0 & k\ge 0 \end{cases}
对式子交换求和符号：
∑d=1n1d∑x=1n∑l≤x∧l+d−1≥xax∑cnt=0n−d1cnt+1∑cntl=0cntl(l−2cntl−1)(n−r−1cnt−cntl−1)\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≥2l\ge 2 且 r≤n−1r\le n-1 时，后面这部分可以直接使用范德蒙德卷积。当 l=1l=1 或者 r=nr=n 时，由于上指数为 −1-1，范德蒙德卷积会出错，所以分开讨论。
更进一步，当讨论 l=1l=1 或 r=nr=n 时，l=1∧r=nl=1\land r=n 会被另外讨论，因为其同样会使此处上指数为 −1-1。
所以将区间分开以下三种情况讨论：
  1. l≥2l\ge 2 且 r≤n−1r\le n-1。
  2. l=1l=1 且 r<nr<n 或 l>1l>1 且 r=nr=n。
  3. l=1l=1 且 r=nr=n。

第一种（l≥2l\ge 2 且 r≤n−1r\le n-1）

原式为
∑d=1n−21d∑x=1n∑2≤l≤x∧x≤l+d−1≤n−1ax∑cnt=0n−d1cnt+1∑cntl=0cntl(l−2cntl−1)(n−r−1cnt−cntl−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)=∑x=1n∑2≤l≤x∧x≤l+d−1≤n−1axb(d)=\sum_{x=1}^n\sum_{2\le l\le x\land x \le l+d-1 \le n-1}a_x
h(D)=∑cnt=2D+21cnt+1(Dcnt−2),D≥2=∑cnt=0D1cnt+3(Dcnt),D≥2\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}
（bb 算贡献，hh 算方案。）
对后面式子使用范德蒙德卷积后，式子为
∑d=1n−21d×b(d)×h(n−d−2)\sum_{d=1}^{n-2} \frac 1 d\times b(d)\times h(n-d-2)
考虑 b(d)b(d) 的计算，将每一个 axa_x 的系数写出来，不难发现递推规律：
b(1)=zn−1−z2b(d)=b(d−1)+zn−d−zd+1,d≥2b(1)=z_{n-1}-z_{2}\\ b(d)=b(d-1)+z_{n-d}-z_{d+1},d\ge 2
（其中zxz_x 为 axa_x 的前缀和数组。）
h(D)h(D) 的推导先放一放。

第二种（l=1l=1 且 r<nr<n 或 l>1l>1 且 r=nr=n）

设 g(D)g(D) 为
g(D)=∑cnt=1D+11cnt+1(Dcnt−1)=∑cnt=0D1cnt+2(Dcnt)\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≥2D\ge 2。）
类似上面的套路推一推，可以如下式子。
l=1l=1 时，贡献为
∑d=1n−1g(n−d−1)×1d×zd\sum_{d=1}^{n-1}g(n-d-1)\times\frac 1 d \times z_d
r=nr=n 时，贡献为
∑d=1n−1g(n−d−1)×1d×(zn−zn−d)\sum_{d=1}^{n-1}g(n-d-1)\times\frac 1 d \times (z_n-z_{n-d})
（其中zxz_x 为 axa_x 的前缀和数组。）
g(D)g(D) 的推导也先放一放。

第三种 （l=1l=1 且 r=nr=n）

显然为
znn\frac {z_n} n

关于 g(D)g(D)，h(D)h(D) 的推导

发现我们是在计算这样的东西：（k=1,2,3,⋯k=1,2,3,\cdots）
∑cnt=0D1cnt+k(Dcnt)\sum_{cnt=0}^{D}\frac 1 {cnt+k} \binom{D}{cnt}
把组合数拆开，发现当 k=1k=1 时，cnt+1cnt+1 刚好可以乘入分母中。将分子先乘上一个 D+1D+1 后，就变为 D+1D+1 该行的组合数。
由于 xx 行的组合数之和为 2x2^x，并且计算时缺少了 D+1D+1 行的最后一项，所以和为 2D+1−12^{D+1}-1。最后再除以回 D+1D+1。
所以
∑cnt=0D1cnt+1(Dcnt)=2D+1−1D+1\sum_{cnt=0}^{D}\frac 1 {cnt+1} \binom{D}{cnt}=\frac{2^{D+1}-1}{D+1}
设
f(D)=∑cnt=0D1cnt+1(Dcnt)\begin{aligned} f(D)&=\sum_{cnt=0}^{D}\frac 1 {cnt+1} \binom{D}{cnt} \end{aligned}
考虑扩展到 k≥2k\ge 2 的情况。
组合数推导式和其对称性，造就了其可以差分的性质。
对于一个 xx，将 xx 行的组合数每个分别减去其 x−1x-1 行同一列的组合数，得到的是 x−1x-1 行组合数向右平移一个位置的序列。
发现此时系数刚好会向右平移 11 格。
k=2k=2 时，可以得到
g(D)=f(D+1)−f(D)g(D)=f(D+1)-f(D)
k=3k=3 时，同理可以得到
h(D)=g(D+1)−g(D)h(D)=g(D+1)-g(D)
（证明直接错位相减即可。）

End

把三种结果加起来，乘上总方案数的倒数（为 12n−1\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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...