[ARC127 E] Pass to Next —— 组合意义+DP容斥+环上DP

本文主要是介绍[ARC127 E] Pass to Next —— 组合意义+DP容斥+环上DP，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

\(n\) 个人排成一个环，第 \(i\) 人有 \(a_i\) 个球。现在，第 \(i\) 个人选择将自己的 \(h_i\;(h_i\in [0,a_i])\) 个球给右边的人 \(j\) \((j=i\%n+1)\)。设过程结束后，第 \(i\) 人拥有的球数为 \(b_i\)。所有可能的情况下的 \(b\) 构成了集合 \(B\)，求 \(\sum_{b\in B}\prod_{i=1}^n b_i\)。

思路

注意到多个相同的 \(b\) 不能算多次，什么情况下 \(h\) 不同的时候 \(b\) 会相同？

对于一个 \(h\)，如果对任意 \(i\)，\(h_i\ge1\)，那么我们将所有 \(h_i\) 都减去 \(1\)，每一个人多给出去一个，也多得到一个，\(b\) 是不变的。即 \(h\) 的差分相同的时候 \(b\) 不变。显然 \(h\) 差分不同的时候 \(b\) 一定会变。

也就是说，只有当存在一个 \(i\)，\(h_i=0\) 的时候，这样的 \(h\) 才要记入答案。

可以容斥，用总方案减去钦定所有 \(h_i\in [1,a_i]\) 的方案，得到的就是至少有一个人不给球的方案。

接下来我们考虑原式的组合意义：对于每种可能分配，完成后每个人再从自己现在所拥有的球中选出一个的总方案。

于是每个人选球可以分成两种情况：1. 从自己没从给出去的球中选；2. 从上一个人给自己的球中选。

分成两种情况后，就可以愉快 dp 了！

约定 \(S(n)=\sum_{i=1}^n i\)，\(T(n)=\sum_{i=1}^n i^2\)。

容斥的两个方案用一种 dp，设变量 \(q=0/1\)，\(q=0\) 表示无限制，\(q=1\) 表示 \(h_i\ge 1\)。

先不考虑环的限制，设状态 \(f[i][j=0/1]\)，表示已经讨论了 \(1\sim i\) 的选球情况，\(j=0\) 表示其中第 \(i\) 个人选择从自己没从给出去的球中选，而 \(j=1\) 表示选择从上一个人给自己的球中选。

每次决策从 \(f[i-1]\) 转移到 \(f[i]\)，就是选择一个 \(k=h_{i-1}\in[q,a_{i-1}]\)，表示 \(i-1\) 给出了 \(k\) 个，\(i\) 得到了 \(k\) 个。

注意到想要计算一个位置 \(i\) 的贡献，就必须知道自己剩下了多少或自己得到了多少。

即 \(f[i][0]\) 实际上只计算了 \(1\sim i-1\) 的贡献，第 \(i\) 个位置要知道自己给出去多少，下一次转移才能计算贡献。

同理，\(f[i][1]\) 就已经计算了 \(1\sim i\) 的贡献，第 \(i\) 个位置只要知道自己得到了多少，这次转移计算。

具体考虑每一个转移：

1. \(f[i][0]\leftarrow f[i-1][1]\)
   \(i-1\) 已经算过贡献，\(i\) 还不能算，于是方案就是 \(k\) 的取值个数，即：

2. \(f[i][1]\leftarrow f[i-1][1]\)
   \(i\) 需要从得到的 \(k\) 个球里面选一个，由 \(k\in [q,a_{i-1}]\) 知贡献为 \(\sum\limits_{k=q}^{a_{i-1}}k\) ，即：

3. \(f[i][0]\leftarrow f[i-1][0]\)
   \(i-1\) 需要从剩下的 \(a_{i-1}-k\) 个球里面选一个，而 \(k'=a_{i-1}-k\in [0,a_{i-1}-q]\) ，则贡献为 \(\sum\limits_{k'=0}^{a_{i-1}-q}k'\) ，即：

4. \(f[i][1]\leftarrow f[i-1][0]\)
   \(i\) 需要从得到的 \(k\) 个球里面选一个，\(i-1\) 也需要从剩下的 \(a_{i-1}-k\) 个球里面选一个，则贡献为 \(\sum\limits_{k=q}^{a_{i-1}}k(a_{i-1}-k)=a_{i-1}\sum\limits_{k=q}^{a_{i-1}}k-\sum\limits_{k=q}^{a_{i-1}}k^2\) ，注意到 \(k=0\) 时贡献为 \(0\) ，即 \(q\) 的值不影响贡献：

接着考虑环的情况，由于 \(n\) 向 \(1\) 的转移一开始不能完成，因为不知道 \(f[n]\) 的值，于是先钦定人 \(1\) 的选球方式，钦定完后暂且将人 \(1\) 的对应贡献就定为 \(1\) ，如此设定初值，转移一圈得到 \(f[n]\) 后补上 \(1\) 真正的贡献。 对初始的 \(1\) 两种选球方式分别 dp 的答案累加即可。

形式化地，定义变量 \(p=0/1\)，\(p=0\) 即 \(1\) 选择自己剩下的球，\(p=1\) 即选择 \(n\) 给的球，

定义初值 \(f[1][0]=\neg p, f[1][1]=p\)，则最后 \(f[1][p]\) 即为所求。

对每个 \(p,q\) 分别计算即可。

代码

#include<bits/stdc++.h>
#define R register int
#define I inline
#define ll long long
using namespace std;
const int N=1e5+3,P=998244353;
int n,a[N],f[N][2];
I ll S(int n){return (n*(n+1ll)>>1)%P;}
I ll T(int n){return n%3==1?(2*n+1)/3*S(n):n*(n+1ll)/6%P*(2*n+1);}
ll dp(bool p,bool q)
{
	f[1][0]=p^1;f[1][1]=p;
	for(R i=1,j;i<=n;i++)
	{
		j=i==n?1:i+1;
		f[j][0]=((a[i]+1ll-q)*f[i][1]+S(a[i]-q)*f[i][0])%P;
		f[j][1]=(S(a[i])*f[i][1]+(a[i]*S(a[i])-T(a[i]))%P*f[i][0])%P;
	}
	return f[1][p];
}
int main()
{
	scanf("%d",&n);
	for(R i=1;i<=n;i++)scanf("%d",a+i);
	ll ans=dp(0,0)-dp(0,1)+dp(1,0)-dp(1,1);
	ans=(ans%P+P)%P;
	printf("%lld\n",ans);
	return 0;
}

这篇关于[ARC127 E] Pass to Next —— 组合意义+DP容斥+环上DP的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！