ARC120F Wine Thief 做题记录

给定一个长 $n$ 的序列 $a$ 和一个正整数 $k$，求所有满足 $S\subseteq \{1,2,3,\dots,n\}$ 且 $\forall i\in S,i+1\not\in S$ 的集合 $S$ 的 $\sum\limits_{i\in S}a_i$ 的和，对 $998244353$ 取模。

$2\le n\le 3\times 10^5$，$1\le k\le \lceil\frac{n}{2}\rceil$。

首先考虑怎么算方案数，显然可以使用插板法，则长 $n$ 的链上大小为 $k$ 的独立集共有 $f(n,k)=\binom{n-k+1}{k}$ 个。

考虑拆贡献计算总和，那么相当于要枚举一个位置 $i$ 并钦定 $a_i$ 在独立集中。

注意到链不好做，人类智慧地考虑环的情况，即令 $a_1$ 和 $a_n$ 也不能同时选，那么此时随便钦定一个 $i$ 必选的方案数都是 $f(n-3,k-1)$。

不过我们算少了 $a_1$ 和 $a_n$ 同时选的情况。对于 $a_1$ 和 $a_n$，它们在少算的情况中的总贡献为 $(a_1+a_n)\times f(n-4,k-2)$；而对于 $a_{[3,n-2]}$，它们少算的贡献相当于 $a'=a_{[3,n-2]},k'=k-2$ 的子问题，递归即可。

不难发现，每次计算都是 $O(1)$ 的，而最多递归 $n$ 次，所以复杂度为 $O(n)$。

边界情况要特判，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=300005;

#define p 998244353

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}
inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

int fra[S],inv[S];
int n,k,d,a[S],s[S];

inline int C(int n,int m)
{
	if(n<0||m<0||n<m) return 0;
	return 1ll*fra[n]*inv[n-m]%p*inv[m]%p;
}
inline int f(int n,int k){return C(n-k+1,k);}

int calc(int l,int r,int k)
{
	if(k<=0) return 0;
	if(r<=l+1) return k!=1?0:(s[r]-s[l-1]+p)%p;
	if(r==l+2)
	{
		if(k==1) return (s[r]-s[l-1]+p)%p;
		if(k==2) return (a[l]+a[r])%p;
		return 0;
	}
	int res=0;
	res=1ll*(s[r]-s[l-1]+p)*f(r-l+1-3,k-1)%p;
	add(res,1ll*(a[l]+a[r])*f(r-l+1-4,k-2)%p);
	add(res,calc(l+2,r-2,k-2));
	return res;
}

int main()
{
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	inv[S-3]=qpow(fra[S-3],p-2);
	for(int i=S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k>>d;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) s[i]=a[i],add(s[i],s[i-1]);
	cout<<calc(1,n,k)<<'\n';
	return 0;
}