前言

赛时一直在做这题但是没推出来呜呜，下次还是不能懒，多打表。一些东西也不要随便化简，可能化简之后反而看不出结论了。

感谢 ciuim 和 NaCly_Fish 等大神在 LA 群教会我做这题。

题目翻译

给定 $n$，求 $(\Large\sum\limits_{j=1}^n\sum\limits_{i=j}^n(C(i,j)\bmod j))\bmod p$。

其中 $p=10^9+7$。

$C(i,j)$ 表示圆排列，即 $\large\binom{i}{j}(j-1)!$。

$n!$ 表示阶乘，即 $n\times (n-1)\times (n-2)\times \dots\times 1$。

$t$ 组询问。

$1\leq t\leq 5\times 10^5,1\leq n\leq 10^6$。与大部分 CF 类型题不一样的是，本题没有对 $\sum n$ 的约束。

题目思路

首先先把题目这个鬼式子打开来。即为

$$
(\Large\sum\limits_{j=1}^n\sum\limits_{i=j}^n(\dfrac{i!(j-1)!}{j!(i-j)!}\bmod j))\bmod p
$$

。

这时容易发现，对于每个 $j$ 分开处理比较好，因为都带一个 $\bmod j$。

然后看到这个时间限制，不难猜测是不劣于 $\mathcal O(n\log n)$ 的解法。

当然虽然没有保证 $\sum n$ 但是我们可以提前把 $[1,10^6]$ 的答案都算出来然后 $\mathcal O(1)$ 回答。

那么我们大概猜测这样一个东西：对于任意 $j$ 在均摊不劣于 $\mathcal O(\log n)$ 时间求出 $\Large(\sum\limits_{i=j}^n(\dfrac{i!(j-1)!}{j!(i-j)!}\bmod j))\bmod p$。

考虑到这个 $\bmod j$ 的循环节什么的，很容易往调和级数上去想。事实上我赛时也推到了这一步。

这个时候集中注意力观察。考虑到这个式子是一个二项式系数乘上一个 $(j-1)!$。那么 $(j-1)! \equiv 0\pmod j$ 是上式为 $0$ 的充分条件。

接下来把注意力再次放大，发现不满足 $j=4\operatorname{or}j\text{ is prime}$ 的 $j$ 贡献都是 $0$。

不满足 $j\text{ is prime}$ 的 $j$ 贡献都是 $0$，这个结论如何证明？

首先 $j=1$ 显然任何数 $\equiv 0\pmod 1$。

然而当 $j$ 是合数且 $j\neq 4$ 的时候，$(j-1)!\equiv 0\pmod j$ 的证明如下。

考虑合数书写是 $a\times b$ 满足 $a\neq 1\operatorname{and} b\neq 1$，那么朴素情况下即 $a\neq b$，显然 $a$ 与 $b$ 分别作为一个因子在 $(j-1)!$ 中出现了。

极端一点，$a=b$，且 $a,b$ 均为质数，这是最不好处理的。

然而，由于对于 $a\gt2$ 的情况，一定可以被证明成 $2a$ 与 $b$ 也分别作为一个因子在 $(j-1)!$ 中出现了。

$a=b=2$ 是最特殊的情况，因此 $4$ 不被包括在这类合数中。

这里有个问题我想了很久，感觉是熬夜打 CF 然后熬夜补题导致的脑子生锈。我们并不是说满足 $(j-1)! \equiv 0\pmod j$ 的才可以满足上式为 $0$。只是说满足 $(j-1)! \equiv 0\pmod j$ 一定满足上式为 $0$，而且可以筛去大部分无用的数。操作起来很方便。

接下来有了这个结论就很好做了。

之后的推导需要『威尔逊定理』和『卢卡斯定理』作为前置知识。

威尔逊定理：对于任意质数 $p$ 满足 $(p-1)!\equiv p-1 \pmod p$。

卢卡斯定理：对于任意质数 $p$ 满足 $\large \binom n m\bmod p=\binom{\lfloor n/p\rfloor}{\lfloor n/m\rfloor}\times \binom{n\bmod p}{m\bmod p}\bmod p$。

$j=4$ 部分很简单，直接按上式算就可以，$\mathcal O(n)$ 解决。乘法过程会炸 long long，可以使用 __int128 解决。

$j\text { is prime}$ 部分，把上面两个定理组合起来，得到 $\Large\binom ij(j-1)!\equiv \binom ij(j-1)\equiv -\binom i j\equiv-\lfloor\frac i j\rfloor\pmod p$。

因此，$[kj,(k+1)j-1]$ 之间产生的贡献是一样的，都是 $-\lfloor\frac i j\rfloor=-k$。

所以我们直接枚举这个 $k$ 即可。区间加法可以使用差分解决。

复杂度是一个类似调和级数的东西。当然，这里只有质数，所以复杂度等同埃筛即 $\mathcal O(n\log \log n)$。

注意做完之后需要再做一次前缀和才能 $\mathcal O(1)$ 回答。

部分代码

https://codeforces.com/contest/1957/submission/257645847

省略了 modint 部分。

注意做完之后需要再做一次前缀和才能 $\mathcal O(1)$ 回答。

所以代码最后出现了 2 次前缀和。第一次是差分操作，第二次是前缀和。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;
using Z = mod_int<P>;
typedef long long ll;
typedef __int128 LL;
const int N = 1e6;
int p[1000020];
bool np[1000020];
Z ans[1000020];
void add(int l, int r, Z w)
{
    ans[l] += w, ans[min(r, N) + 1] -= w;
}
void solve()
{
    int n;
    cin >> n;
    cout << ans[n] << '\n';
}
int main()
{
    np[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!np[i])
            p[++p[0]] = i;
        for (int j = 1; j <= p[0] && i * p[j] <= N; j++)
        {
            np[i * p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
    for (int j = 1; j <= N; j++)
    {
        if (np[j])
        {
            if (j == 4)
            {
                for (LL k = 4; k <= N; k++)
                    add(k, k, k * (k - 1) * (k - 2) * (k - 3) / 4 / 3 / 2 / 1 * 3 * 2 * 1 % 4);
            }
            continue;
        }
        for (int k = 1; k * j <= N; k++)
            add(k * j, (k + 1) * j - 1, (-k % j + j) % j);
    }
    for (int i = 1; i <= N; i++)
        ans[i] += ans[i - 1];
    for (int i = 1; i <= N; i++)
        ans[i] += ans[i - 1];
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}