• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 7小时前 4次浏览

题目描述

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

思路

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

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

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

可以容斥,用总方案减去钦定所有 (h_iin [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_ige 1)

先不考虑环的限制,设状态 (f[i][j=0/1]),表示已经讨论了 (1sim 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]) 实际上只计算了 (1sim i-1) 的贡献,第 (i) 个位置要知道自己给出去多少,下一次转移才能计算贡献。

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

具体考虑每一个转移:

  1. (f[i][0]leftarrow f[i-1][1])
    (i-1) 已经算过贡献,(i) 还不能算,于是方案就是 (k) 的取值个数,即:
[f[i-1][1]times (a_{i-1}-q+1)
]

  1. (f[i][1]leftarrow f[i-1][1])
    (i) 需要从得到的 (k) 个球里面选一个,由 (kin [q,a_{i-1}]) 知贡献为 (sumlimits_{k=q}^{a_{i-1}}k) ,即:
[f[i-1][1]times S(a_{i-1})
]

  1. (f[i][0]leftarrow f[i-1][0])
    (i-1) 需要从剩下的 (a_{i-1}-k) 个球里面选一个,而 (k’=a_{i-1}-kin [0,a_{i-1}-q]) ,则贡献为 (sumlimits_{k’=0}^{a_{i-1}-q}k’) ,即:
[f[i-1][0]times S(a_{i-1}-q)
]

  1. (f[i][1]leftarrow f[i-1][0])
    (i) 需要从得到的 (k) 个球里面选一个,(i-1) 也需要从剩下的 (a_{i-1}-k) 个球里面选一个,则贡献为 (sumlimits_{k=q}^{a_{i-1}}k(a_{i-1}-k)=a_{i-1}sumlimits_{k=q}^{a_{i-1}}k-sumlimits_{k=q}^{a_{i-1}}k^2) ,注意到 (k=0) 时贡献为 (0) ,即 (q) 的值不影响贡献:
[f[i-1][0]times (a_{i-1}S(a_{i-1})-T(a_{i-1}))
]

接着考虑环的情况,由于 (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("%lldn",ans);
	return 0;
}

程序员灯塔
转载请注明原文链接:[ARC127 E] Pass to Next —— 组合意义+DP容斥+环上DP
喜欢 (0)