https://codeforces.com/contest/1957/problem/E
题意
记 \(Q_n^k\) 为在 \(n\) 个数中选 \(r\) 个数排列成一圈的方案数，即圆排列数。求
\[\sum_{i=1}^n\sum_{j=1}^i Q_i^j\ \mathrm{mod} \ j \]对 \(10^9+7\) 取余的结果。
思路
这种模数变来变去的题，要考虑打表。
圆排列
\[Q_i^j=\frac{A_i^j}j=\frac{i(i-1)\cdots (i-j+1)}{j} \]注意到分子是连续 \(j\) 个数的乘积，那么其中必有一个是 \(j\) 的倍数，记为 \(kj\)，则
\[Q_i^j\ \mathrm{mod} \ j=\frac{i\cdots (kj+1)\cdot kj\cdot (kj-1)\cdots(i-j+1)}{j}\ \mathrm{mod} \ j \]\(kj/j=k=\lfloor i/j\rfloor\)，分子中的其它项对 \(j\) 取余后是 \(\cdots 3\cdot 2\cdot 1\cdot -1\cdot -2\cdots \ (\mathrm{mod} \ j)\)，即 \((j-1)!\ \mathrm{mod} \ j\)
题目中的和式变为
\[\sum_{i=1}^n\sum_{j=1}^i \lfloor\frac ij\rfloor (j-1)!\ \mathrm{mod} \ j \]由威尔逊定理，
\[(j-1)!\ \mathrm{mod} \ j= \begin{cases} 2 &j=4 \\ j-1 &j为素数\\ 0 &其它 \end{cases} \]然后交换求和顺序，数论分块
记
\[f(i)=\sum_{j=1}^i \lfloor\frac ij\rfloor (j-1)!\ \mathrm{mod} \ j \]答案就是数组 \(f\) 的前缀和。考虑每个 \(j\)（\(j=4\) 或 \(j\) 为素数）对那些 \(f(i)\) 产生多少贡献：\(j\) 会让 \(i\in[kj,(k+1)j)\) 都加上 \(\lfloor\frac ij\rfloor (j-1)!\ \mathrm{mod} \ j\)。区间加，用差分实现。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5, P = 1e9 + 7;
bool notPri[N];
ll f[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for (int j = 2; j < N; ++j) {
if (!notPri[j] || j == 4) {
for (int i = j; i < N; i += j) {
notPri[i] = true;
ll d = 1ll * i / j * (j == 4 ? 2 : j - 1) % j;
(f[i] += d) %= P;
if (i + j < N) (f[i + j] += P - d) %= P;
}
}
}
for (int i = 1; i < N; ++i) (f[i] += f[i - 1]) %= P; //对差分数组做前缀和得到f
for (int i = 1; i < N; ++i) (f[i] += f[i - 1]) %= P; //对f做前缀和得到答案
int T; cin >> T; while (T--) {
int n; cin >> n;
cout << f[n] << '\n';
}
return 0;
}