ARC124E 题解

· · 题解

看到 \sum \prod 状物直接想组合意义。具体地，我们计算在操作之后，从每个人手中挑出一个球的方案数。

考虑令 f_{i,0/1} 为 i 手中的球为原本有的，不计算 i 从中选出一个球/上一个人给球，算 有多少种方案从 i-1 手里拿球的方案数。二者均不考虑 i 传几个给 i+1。转移分以下几类：

令 \sum \limits_{j=1}^{n} j^2 为 S_2(n)，\sum \limits_{j=1}^n j 为 S_1(n)

f_{i,0} \leftarrow f_{i-1,0} S_1(a_{i-1})+f_{i-1,1}(a_{i-1}+1)

对于 f_{i-1,0}，额外结算其给 i 的方案数以及自己拿的方案数，则为 \sum \limits_{i=0}^{a_{i-1}}(a_{i-1}-i)。对于 f_{i-1,1} 则给球的方案数有给 0 个到 a_{i-1} 个共 a_{i-1}+1 种方案。

f_{i,1} \leftarrow f_{i-1,0}(a_{i-1}S_1(a_{i-1})-S_2(a_{i-1}))+f_{i-1,1}S_1(a_{i-1})

对于 f_{i-1,0}，首先计算给 i 多少个，然后分别算 i-1 的选择方案数以及 i 的选择方案数，为 \sum \limits_{i=0}^{a_{i-1}} (a_{i-1}-i)i。对于 f_{i-1,1}，直接枚举给多少个，计算 i 的选择方案数，为 \sum \limits_{i=1}^{a_{i-1}} i。

枚举 1 的来源，则边界条件为 f_{1,0}=1,f_{1,1}=0 或 f_{1,1}=1,f_{1,0}=0。最后再额外处理一个 f_{n+1} 返回即可。

但是这玩意是不对的。记 i 给出去的球的个数为 c_i，则其认为的方案本质不同当且仅当给出去的个数不同。该怎么办呢？

断言：\min c_i =0 的方案与最终的 b 序列一一对应。

证明：显然一种 c 序列唯一对应一种 b 序列。当 b 序列给定时，其就相当于 c_{i-1}-c_i=\Delta b_i。所以差分数组给定，唯一的差别就是基准元的值。钦定最小的数为 0 即可对应。

考虑容斥，即把无限制的减去 \min \ge 1 即可。

时间复杂度 O(n)。