ARC124E 题解

· · 题解

设操作序列为 x_i，即为每个人向右传递的球数，则传完球的序列 b_i=a_i-x_i+x_{i-1}，发现后边其实是 x_i 的差分，所以答案只与差分相关，所以我们只统计 \min x_i=0 的操作序列，因为所有 \min x_i>0 的情况都可以通过使所有 x_i 减去 \min x_i 来实现转化，如果统计 \min x_i=0 的话，只需要容斥一下，分别统计所有 x_i\in[0,a_i] 的情况和所有 x_i\in[1,a_i] 的权值相减即可。

考虑答案：

f_n=\prod_{i=1}^n (a_i-x_i+x_{i-1})

如果考虑转移的话，那么就可以展开第 n 项得到：

a_n\prod_{i=1}^{n-1} (a_i-x_i+x_{i-1})-x_n\prod_{i=1}^{n-1} (a_i-x_i+x_{i-1})+x_{n-1}\prod_{i=1}^{n-1} (a_i-x_i+x_{i-1})

因为 a_n 和 x_n 与前边项无关，又因为 x_n\in [0,a_i]，所以前两项为 a_nf_{n-1} 和 \left(\sum_{i=0}^{a_n}i\right)\cdot f_{n-1}，但是在第三项出现了问题，我们单独将它拿出来审视，设：

g_n=x_n\prod_{i=1}^n (a_i-x_i+x_{i-1})

考虑它的转移，也拆开第 n 项来分析：

x_na_n\prod_{i=1}^{n-1} (a_i-x_i+x_{i-1})-x_n^2\prod_{i=1}^{n-1} (a_i-x_i+x_{i-1})+x_nx_{n-1}\prod_{i=1}^{n-1} (a_i-x_i+x_{i-1})

然后发现，x_na_n，x_n^2 与前边项无关，直接统计即可，观察最后一项其实就是 x_ng_{n-1}，从之前转移即可。

将前边的两个递推公式综合起来可得：

f_n=S_1(a_n)f_{n-1}+(a_n+1)g_{n-1} g_n=(a_nS_1(a_n)-S_2(a_n))f_{n-1}+S_1(a_n)g_{n-1}

然后枚举断点情况和 x_i 值域情况容斥即可。