CF1957E Carousel of Combinations

求
$$
\sum_{i=1}^{n}\sum_{j=1}^{i}C(i,j)\bmod j
$$
其中 $𝐶(𝑖,𝑗)$ 表示从 $i$ 个数当中选 $j$​ 个的不同圆排列数。

---

显然，
$$
C(i,j) = \binom{i}{j}(j-1)!
$$
首先，根据威尔逊定理：

当 $p$ 为质数：
$$
(p-1)!\equiv-1 \ (\bmod \ n)
$$
当 $p = 4$ 时：
$$
(p-1)!\equiv 2 \ (\bmod \ n)
$$
当 $p$ 为非 $4$ 合数：
$$
(p-1)!\equiv 0 \ (\bmod \ n)
$$
所以只需要考虑 $j=4$ 或 $j$ 为质数的情况。

根据卢卡斯定理：当 $p$ 为质数时
$$
\binom{n}{m} \equiv \binom{\left \lfloor \frac{n}{p} \right \rfloor }{\left \lfloor \frac{m}{p} \right \rfloor }\binom{n\bmod p}{m\bmod p} \ (\bmod \ p)
$$
所以当 $j$ 是质数时，题目中的
$$
\binom{i}{j} \equiv \left \lfloor \frac{i}{j} \right \rfloor\ (\bmod j)
$$
于是，
$$
C(i,j) \equiv \left \lfloor \frac{i}{j} \right \rfloor(j-1) \ (\bmod j)
$$
题目中没有保证 $\sum n$ 的大小，所以我们要提前预处理出所有的 $n$

我们可以分别算出每个 $i$ 的 $\sum_{j=1}^{i}C(i,j)$ 然后做前缀和

对于每个质数 $j$，对 $[kj,(k+1)j)$ 的 $i$ 的贡献都是相同的，可以用差分来离线完成区间加

当 $j=4$ 时
$$
C(i,4) \equiv 2\binom{i}{4}\ (\bmod 4)
$$