526互联

Atcoder Regular Contest 124 E - Pass to Next

发布时间 2023-07-21 12:29:00作者: tzc_wk

首先第一步是一个浅显的观察：我们要求的是所有可能的最终序列的贡献之和，如果能改为计算所有操作序列的贡献之和那问题会简单很多，并且我们惊奇地发现，如果一组 \(x_i\) 全大于 \(0\)，那么把它们全减去 \(1\) 以后得到的答案序列不会改变，而对于任意一种可能的最终序列，必然存在一组 \(\min x_i=0\) 的操作序列能够得到这个答案序列。也就是说我们建立了一组 \(\min x_i=0\) 的答案序列到操作序列的映射。那么具体怎么计算这个东西呢？我们计算所有操作序列的答案之和，再将所有 \(b_i\) 减一，计算新的操作序列之和，二者做差就是答案。

转换贡献体，改为每个人选一个目前在手中的球，计算选择的方案数。

每个人选择的球有两种情况，一是上一个人传过来的，二是自己原有的。

先考虑链的情况，我们设 \(dp_{i,0/1}\) 表示考虑到第 \(i\) 个人，第 \(i\) 个人考虑自己原有的 / 上一个人传过来的球的方案，所有已经确定贡献的方案数。注意，之所以说已经确定的贡献，是因为如果第 \(i\) 个人考虑自己原有的球，那么有可能下一个人考虑上一个人（也就是 \(i\)）传过来的球，那么我们把第 \(i\) 个人传球的方案放到 \(i+1\) 那里计算，这样第 \(i\) 个人的方案就不算“已经确定贡献”的方案。转移显然：

  • \(dp_{i-1,1}·(a_i+1)\to dp_{i,0}\)
  • \(dp_{i-1,0}·(\sum_{j=0}^{a_i} j)\to dp_{i,0}\)
  • \(dp_{i-1,1}·(\sum_{j=0}^{a_i} j)\to dp_{i,1}\)
  • \(dp_{i-1,0}·(\sum_{j=0}^{a_i} (a_i-j)·j)\to dp_{i,1}\)

还有一个问题就是环的情况。其实很简单，强制钦定第 \(1\) 个人是原有的还是传过来的就行了。代码里有个 \(-1\) 是因为我给 \(dp_{1,c1}\) 赋了 \(1\) 的初值，这个初值不能算入答案。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5;
const int MOD=998244353;
const int INV6=(MOD+1)/6;
int n,a[MAXN+5],dp[MAXN+5][2];
int getsum1(int x){return 1ll*x*(x+1)/2%MOD;}
int getsum2(int x){return 1ll*x*(x+1)%MOD*(2*x+1)%MOD*INV6%MOD;}
int calc(int c1,int c2){
	memset(dp,0,sizeof(dp));dp[1][c1]=1;
	for(int i=1;i<=n;i++){
		dp[i%n+1][0]=(1ll*dp[i][0]*getsum1(a[i]-c2)+1ll*dp[i][1]*(a[i]-c2+1))%MOD;
		dp[i%n+1][1]=(1ll*dp[i][0]*(1ll*a[i]*getsum1(a[i])%MOD-getsum2(a[i])+MOD)+1ll*dp[i][1]*getsum1(a[i]))%MOD;
	}return (dp[1][c1]-1+MOD)%MOD;
}
int main(){
	scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	printf("%d\n",(0ll+calc(0,0)+calc(1,0)-calc(0,1)-calc(1,1)+MOD+MOD)%MOD);
	return 0;
}