ARC124E Pass to Next 题解

题意

\(n\) 个人，每人 \(a_i\) 个球，每个人同时传若干个球给下一个人（不多于手中的，可以不传），得到序列 \(a‘\) ，求 \(\sum_{a‘}\prod_{i=1}^na‘_i\bmod 998244353\) 。

\((3\le n\le10^5,0\le a_i\le10^9)\)

题解

首先不管后面的 \(\prod\) ，求有多少种序列：

首先每个人能传球的个数 \(x\) 都满足 \(0\le x\le a_i\) 。

考虑将所有人传球数量均减少 \(1\) ，序列不变，所以如果钦定每次传球必须有 \(0\) 得到的序列就不会重复。

考虑计算答案的时候进行容斥，先不加任何限制算贡献，再减掉所有不能有 \(0\) 的方案的贡献。

现在来考虑 \(\prod a‘_i\) 怎么算：这个东西的组合意义是在传出来的若干个球中再选一个球出来，知道了这个组合意义后来 DP ：

主要是设 \(f(i,0)\) 为在 \(i\) 自己的球里选一个，前 \(i-1\) 人的方案， \(f(i,1)\) 为在前面人的球里选一个，前 \(i\) 人的方案。

注意如果 \(f(i,1)\) ，第 \(i-1\) 个人是强制向第 \(i\) 个人传了球的。

具体的转移见代码把，没必要照着念一遍……之后不难推了

时间复杂度 \(O(n)\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=998244353,iv3=(mod+1)/3;
int n,a[N],f[N][2];
int calc(int x,int y){
	memset(f,0,sizeof(f));f[0][x]=1;
	for(int i=0;i<n;i++){
		int g=a[i]-y,c=(g+1ll)*g/2%mod;
		f[i+1][0]=(1ll*c*f[i][0]+(g+1ll)*f[i][1])%mod;
		g+=y;c=(g+1ll)*g/2%mod;int ss=c*(g-1ll)%mod*iv3%mod;
		f[i+1][1]=(1ll*c*f[i][1]+1ll*ss*f[i][0])%mod;
	}
	return f[n][x];
}
signed main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	printf("%lld\n",(calc(0,0)+calc(1,0)-calc(0,1)-calc(1,1)+2ll*mod)%mod);
	return 0;
}

ARC124E Pass to Next 题解

原文：https://www.cnblogs.com/shrshrshr/p/15253074.html