首页 > 其他 > 详细

ARC124E Pass to Next 题解

时间:2021-09-12 12:44:33      阅读:8      评论:0      收藏:0      [点我收藏+]

题意

\(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

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!