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)

。

文章操作

相关推荐

评论

ARC124E 题解