由圆排列的公式，不难有\(C(n,k)=(_k^n)\times \frac{k!}{k}\)
于是答案为\(\sum_{i=1}^{n}\sum_{j=1}^{i}((_j^i)\cdot (j-1)!)mod\space j\)
显然交换求和次序，有\(\sum_{i=1}^{n}\sum_{j=i}^{n}((_i^j)\cdot (i-1)!)mod\space i\)
由威尔逊定理可将\(i\)限定在质数和\(4\)之中，再由卢卡斯定理（这个一定要手写写出来才会发现很容易化简，比赛的时候就觉得可以用程序去算就没有化简，从而导致根本没办法往下面做，所以以后遇到公式了一定要手写写出来）可化简为\(\sum_{i=1}^{n}\sum_{j=i}^{n}(\lfloor\frac{j}{i}\rfloor\cdot (i-1))mod\space i\)
补题的时候一直想的是每个\(i\)对整体的贡献，但是题解告诉我们也可以考虑\(i\)对特定局部的贡献，最后将所有局部汇总就好了
具体来说，这里反过去考虑\(\sum_{i=1}^{n}\sum_{j=1}^{i}((_j^i)\cdot (j-1)!)mod\space j\)，设\(dp[i]=\sum_{j=1}^{i}((_j^i)\cdot (j-1)!)mod\space j\)，再考虑\(\sum_{i=1}^{n}\sum_{j=i}^{n}(\lfloor\frac{j}{i}\rfloor\cdot (i-1))mod\space i\)，统计每个\(i\)对\(dp\)数组的贡献（枚举倍数利用差分），时间复杂度为\(O(n\) ln \(n)\)
标签：化简,frac,space,cdot,sum,Carousel,Combinations,mod From： https://www.cnblogs.com/dingxingdi/p/18312478