【观察，计数 DP，组合意义，拆分，容斥，环上 DP】[ARC124E] Pass to Next
ZillionX
·
·
题解
Description
有 n 个人排成一个环传球，第 i 个人初始球数为 a_i，每个人同时把求传给下一个人（即不能将上一个人传给自己的球传给下一个人），对所有不同的最终局面，设第 i 个人的最终球数为 b_i，求 \sum\limits_b \prod\limits_{i=1}^n b_i。
# Solution
不是很懂矩乘转移的做法，这里是官方题解所述简洁的 DP 做法。
本题的转化和优化手段非常之多，同时 DP 状态定义也非常抽象，本题解将试图具体地讲清楚整道题的解决过程。
------------
首先，我们考虑在操作序列 $x_i$（表示第 $i$ 人向第 $i \bmod n+1$ 人的传球数）和最终状态 $b_i$ 间建立映射。
不难发现，若每个 $x_i$ 皆为正数，则我们把所有 $x_i$ 都减去 $1$ 所对应的 $b_i$ 相同。因此，定义存在至少一个人不传球的操作序列为**好的操作序列**。则好操作序列 $x'_i$ 和最终局面 $b_i$ 间存在双射。
下面我们将在 DP 时对每个人都传球的方案进行容斥，先忽略掉这部分内容。
我们考虑怎么方便地算出 $\prod b_i$，不妨考虑其组合意义：在每种最终局面中，从每个人最终的球中拿走一个的方案数。注意到这个计数问题要两部分组成：确定最终局面 + 选走球，我们设计 DP 来解决这个问题。
将球数设计在状态中是一种不可行的行为，完全没有办法对其进行优化。我们可以考虑最终局面中每个人的球的来源：他首先可以拿走自己原来的球，其次又可以拿上一个人传过来的球。
不难发现这两部分互不相干，第一部分只和下一个人有关，第二部分只和上一个人有关，我们可以把它们拆开来 DP。
设 $f_{i,0}$ 表示第 $i$ 个人选原有的球，考虑前 $i-1$ 人选球的方案数；$f_{i,1}$ 表示第 $i$ 个人选传来的球，考虑前 $i$ 人选球的方案数。
这样设计是为了方便考虑第 $i$ 人向第 $i+1$ 人（选前一人传球）的转移。
设 $s_k(n)$ 表示 $\sum\limits_{i=1}^n i^k$。
有转移
$$f_{i+1,0} \leftarrow f_{i,0} \cdot s_1(a_i) + f_{i,1 }\cdot (a_i+1)$$
$$f_{i+1,1} \leftarrow f_{i,0} \cdot (a_i \cdot s_1(a_i) - s_2(a_i)) + f_{i,1} \cdot s_1(a_i)$$
上面那部分的前半即考虑第 $i$ 人的选择，后半即直接考虑传球的方案。
下面那部分的前半可以考虑第 $i$ 人送出 $x$ 个球，则贡献为 $\sum x (a_i-x)$，后半即考虑直接选定第 $i$ 人送出的球数。
现在我们再次回到前面被忽略的部分，可以发现直接在 $f_{i+1,0}$ 的转移中将 $a_i$ 减去 $1$ 则可以得到钦定所有人都传球的方案数。然后简单容斥即可。
现在我们遇到了最后一个很麻烦的问题，该问题并不是一个序列而是一个环，DP 要怎么初始化才能算出正确答案。我们可以对 $f_{1,0}$ 和 $f_{1,1}$ 分别初始化成 $1$，然后互不干扰地算出各自的答案，再减去 $1$ 即为最终解，具体实现可以参考代码。
时间复杂度线性。
# Code
```cpp
const int N=1e5+5,mo=998244353;
int n,a[N],f[N][2];
int qpow(int x,int y=mo-2) {
int mul=1;
while (y) {
if (y&1) mul=mul*x%mo;
x=x*x%mo,y>>=1;
}
return mul;
}
const int iv2=qpow(2),iv6=qpow(6);
int S(int x) {
return x*(x+1)%mo*iv2%mo;
}
int G(int x) {
return x*(x+1)%mo*(x*2+1)%mo*iv6%mo;
}
int calc(int w1,int w2) {
mes(f);
f[1][0]=w1,f[1][1]=w1^1;
for (int i=1;i<=n;i++) {
int v=i%n+1,w=a[i]-w2;
ad(f[v][0],f[i][0]*S(w)%mo);
ad(f[v][0],f[i][1]*(w+1)%mo);
if (w2) w++;
ad(f[v][1],f[i][0]*de(w*S(w)%mo,G(w))%mo);
ad(f[v][1],f[i][1]*S(w)%mo);
}
return (w1?f[1][0]:f[1][1])-1;
}
signed main() {
scanf("%lld",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
printf("%lld",de((calc(1,0)+calc(0,0))%mo,(calc(0,1)+calc(1,1))%mo));
return 0;
}
```