专栏文章

ARC124E Pass to Next 题解

CCoffee_zzz/xin
AT_arc124_e题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min6f5gy
此快照首次捕获于
2025/12/01 21:19
3 个月前
此快照最后确认于
2025/12/01 21:19
3 个月前
查看原文
设第 ii 个人给下一个人传了 cic_i 个球，第 ii 个人的手中最终有 xix_i 个球，则有 xi=ai−ci+ci−1x_i=a_i-c_i+c_{i-1}，其中我们认为 c0=cnc_0=c_n。显然，若 min⁡i=1nci>0\min\limits_{i=1}^n c_i \gt 0 则可以通过使所有 cic_i 都减去 11 的方式保持最终局面不变，而所有 min⁡i=1nci=0\min\limits_{i=1}^n c_i=0 所形成的最终局面又两两不同，也就是说所有 min⁡i=1nci=0\min\limits_{i=1}^n c_i=0 的操作序列 cc 与最终局面 xx 形成了双射。因此，我们考虑转化计数对象：对于所有 ci∈[0,ai]c_i \in [0,a_i] 且 min⁡i=1nci=0\min\limits_{i=1}^n c_i=0 的数列 cc，计算 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 的和。
先上一个经典手法，把所有 ci∈[0,ai]c_i \in [0,a_i] 且 min⁡i=1nci=0\min\limits_{i=1}^n c_i=0 的数列 cc 的 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和转化为，所有 ci∈[0,ai]c_i \in [0,a_i] 的数列 cc 的 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和减去所有 ci∈[1,ai]c_i \in [1,a_i] 的数列 cc 的 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和。
接下来尝试计算所有 ci∈[0,ai]c_i \in [0,a_i] 的数列 cc 的 ∏i=1n(ai−ci+ci−1)\prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和。考虑其组合意义：对于所有最终局面，从每个人手中选一个球的方案数。
设 fif_i 表示考虑完前 i−1i-1 个人且第 ii 个人选择了自己的球的方案数，gig_i 表示考虑完前 ii 个人且第 ii 个人选择了上一个人传来的球的方案数。这样设计状态是因为，若第 ii 个人选择了自己的球，则其贡献需要在 fif_i 向 fi+1f_{i+1} 或 gi+1g_{i+1} 转移时计算，而若第 ii 个人选择了上一个人传来的球，则其贡献需要在 fi−1f_{i-1} 或 gi−1g_{i-1} 向 gig_i 转移时计算。
转移方程为：
  • fi+1←fi⋅∑v=0aiv+gi⋅∑v=0ai1f_{i+1} \leftarrow f_i \cdot \sum\limits_{v=0}^{a_i} v+g_i \cdot \sum\limits_{v=0}^{a_i} 1（枚举留下几个球）；
  • gi+1←fi⋅∑v=0aiv(ai−v)+gi⋅∑v=0aivg_{i+1} \leftarrow f_i \cdot \sum\limits_{v=0}^{a_i} v(a_i-v)+g_i \cdot \sum\limits_{v=0}^{a_i} v（枚举传了几个球）。
由于这是一个环，所以我们还需要枚举一下第 11 个人的状态：先初始化 f1=1,g1=0f_1=1,g_1=0，dp 一轮，给答案加上 fn+1f_{n+1}；再初始化 f1=0,g1=1f_1=0,g_1=1，重新 dp 一轮，给答案加上 gn+1g_{n+1}。
解决了 ci∈[0,ai]c_i \in [0,a_i] 的情况，ci∈[1,ai]c_i \in [1,a_i] 的情况是基本相同的，但由于要求每个人都要传递至少一个球，所以转移方程变为了：
  • fi+1←fi⋅∑v=0ai−1v+gi⋅∑v=0ai−11f_{i+1} \leftarrow f_i \cdot \sum\limits_{v=0}^{a_i-1} v+g_i \cdot \sum\limits_{v=0}^{a_i-1} 1（枚举留下几个球）；
  • gi+1←fi⋅∑v=1aiv(ai−v)+gi⋅∑v=1aivg_{i+1} \leftarrow f_i \cdot \sum\limits_{v=1}^{a_i} v(a_i-v)+g_i \cdot \sum\limits_{v=1}^{a_i} v（枚举传了几个球）。
其余部分都是一样的，按照上面的方法计算即可。
时间复杂度 O(n)\mathcal O(n)。
C
const int N=3e5+5,mod=998244353,inv2=499122177,inv6=166374059;
int n,a[N],f[N],g[N];
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
int s1(int x){
	return 1ll*x*(x+1)%mod*inv2%mod;
}
int s2(int x){
	return 1ll*x*(x+1)%mod*(x+x+1)%mod*inv6%mod;
}
int work(int x,int y){
	if(!x) f[1]=1,g[1]=0;
	else f[1]=0,g[1]=1;
	for(int i=1;i<=n;i++){
		f[i+1]=ad(1ll*f[i]*s1(a[i]-y)%mod,1ll*g[i]*(a[i]-y+1)%mod);
		g[i+1]=ad(1ll*f[i]*ad(1ll*a[i]*s1(a[i])%mod,mod-s2(a[i]))%mod,1ll*g[i]*s1(a[i])%mod);
	}
	if(!x) return f[n+1];
	else return g[n+1];
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cout<<ad(ad(work(0,0),work(1,0)),mod-ad(work(0,1),work(1,1)))<<endl;
}

评论

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

正在加载评论...