第二种把 `(inv(i,p)%p+p) % p` 改成 `(inv(i,p)+p) % p` 甚至能过 /fad
[记录](https://www.luogu.com.cn/record/59377477)
by baiABC @ 2021-10-07 13:59:10
Cu Ball 系数范围（
by MatrixGroup @ 2021-10-07 13:59:50
求出来的x是完全相同的
by CE_WA_TLE @ 2021-10-07 16:14:08
@[CE_WA_TLE](/user/95612) 是的，但不知道为什么
by baiABC @ 2021-10-07 17:13:43
因为对于一个序列 $b_1,...,b_n$，定义
$$x_i=\begin{cases}
0&i=1
\\
1&i=2
\\
b_{i-1}x_{i-1}+x_{i-2}&i>2
\end{cases}$$
如果令 $a_i$ 为每一次的 $-a/b$ （也就是```s```里存的东西）那么 $x_n$ 就是求出的```x```
可以发现，序列的首项与末项不会造成贡献。
现在定义 $g(l,r)$
表示将原序列 $a$ 的子序列 $a_l,...,a_r$ 带入到 $b$ 中时求出的结果，那么 $g(l,l)=0,g(l,l+1)=1$ 。
根据定义，当 $r>l+1$ 时 $g(l,r)=a_{r-1}g(l,r-1)+g(l,r-2)$
同时观察序列第二项（$a_{l+1}$）对 $g(l,r)$ 的贡献可以发现 $g(l,r)=a_{l+1}g(l+1,r)+g(l+2,r)$
然后发现这两个转移是对称的，也就是说将原序列反过来不会造成影响。
by CE_WA_TLE @ 2021-10-07 18:17:49
@[CE_WA_TLE](/user/95612) 谢谢 dalao
by baiABC @ 2021-10-07 21:40:46