自动搬运

查看原文

来自洛谷，原作者为

	cosf 省选挂48分

搬运于2025-08-24 23:13:29，当前版本为作者最后更新于2025-04-13 19:02:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们可以对 $i$ 分类讨论。当 $i \ge 2$ 时，所有的情况都相似，仅有一个系数的差别。

因为 $v$ 只有 $M!$ 种取值，所以我们先化简 $E \times M!$，最后再除掉就行了。也就是，我们要计算：

1. $\sum_{k=1}^V\left(\sum_{v \text{ is a permutation of }[M]}\sum_{j=1}^N[v_k(j) = j]\right)$
2. $\sum_{k=1}^V\left(\sum_{v \text{ is a permutation of }[M]}\sum_{j=1}^N[v_k(j) = 2j]\right)$

由期望的线性性，所有合理范围内的 $j$ 贡献都是一样的。因此，第一个式子中，我们只需算出 $1$ 的贡献，乘上 $N$ 即可。第二个式子中，算出 $1$ 的贡献，乘上 $\min\left\{N, \frac{M}{2}\right\}$ 即可。

第一个式子

定义排列 $v$ 上的一个环为由不同数字组成的序列 $\{a_1, a_2, \dots, a_m\}$，使得 $v(a_1) = a_2, v(a_2) = a_3, \dots, v(a_m) = a_1$，其中 $m$ 是环长。可以发现，一个排列总能被唯一划分成若干个环。

那么，当 $k$ 确定时，问题可以描述为：“有多少个排列 $v$，$1$ 所在的环的长度是 $k$ 的因数”。

则，我们可以枚举环长 $m$，则对于所有的 $m$ 的倍数 $k$，它的贡献是 $A_{M - 1}^{m - 1} \times (M - m)! = (M - 1)!$。这个值和 $m$ 无关，所以 $m$ 的贡献是 $\lfloor\frac{V}{m}\rfloor \times (M - 1)!$。那么，最终和式的值就是 $(M - 1)! \times \sum_{m=1}^M\lfloor\frac{V}{m}\rfloor$。

除去 $M!$ 之后，$E = \frac{N}{M} \times \sum_{m=1}^M\lfloor\frac{V}{m}\rfloor$，可以 $O(\sqrt{V})$ 计算。

第二个式子

我们只需要 $1$ 和 $2$ 在同一个环即可。当 $k$ 和 $m$ 确定的时候，$1$ 和 $2$ 在环内的相对位置是固定的。将 $1$ 设定为 $a_1$，若 $2$ 位于 $a_j$，则 $j$ 就必须满足 $j - 1 \equiv k \pmod m$。这也说明 $k$ 不能是 $m$ 的倍数。

当 $k$ 不为 $m$ 的倍数时，有 $A_{M - 2}^{m - 2} \times (M - m)! = (M - 2)!$ 个这样的排列。这样的 $k$ 一共有 $V -\lfloor\frac{V}{m}\rfloor$ 个，因此，$m$ 的贡献就是 $(M - 2)! \times (V - \lfloor\frac{V}{m}\rfloor)$。答案即 $\frac{\min\{N, \lfloor\frac{M}{2}\rfloor\}}{M(M - 1)} \times \left(MV - \sum_{m=1}^M\lfloor\frac{V}{m}\rfloor\right)$。同样可以在 $O(\sqrt{V})$ 的时间内算完。

当 $i \ge 3$ 时，这个式子就是 $\frac{\min\{N, \lfloor\frac{M}{i}\rfloor\}}{M(M - 1)} \times (MV - \sum^{M}_{m = 1}\lfloor\frac{V}{m}\rfloor)$，后面的一项和 $i$ 无关，前面的同样在 $O(\sqrt{M})$ 的复杂度内算出来。

更新：有个式子写错了。

std

#include <iostream>
using namespace std;

#define MOD 998244353ll

using ll = long long;

ll pow(ll b, ll p, ll m)
{
    b %= MOD;
    ll r = 1;
    while (p)
    {
        if (p & 1)
        {
            r = r * b % m;
        }
        b = b * b % m;
        p >>= 1;
    }
    return r;
}

ll inv(ll p)
{
    return pow(p, MOD - 2, MOD);
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n, m, v;
        cin >> n >> m >> v;
        ll s = 0;
        for (ll l = 1, r; l <= m && l <= v; l = r + 1)
        {
            r = min(m, v / (v / l));
            s = (s + (r - l + 1) % MOD * (v / l % MOD) % MOD) % MOD;
        }
        ll mid = m / n;
        ll res = (mid - 1) % MOD * (n % MOD) % MOD;
        for (ll l = mid + 1, r; l <= m; l = r + 1)
        {
            r = m / (m / l);
            res = (res + (r - l + 1) % MOD * (m / l % MOD) % MOD) % MOD;
        }
        cout << (res * (((m % MOD) * (v % MOD) % MOD - s + MOD) % MOD) % MOD * inv(m % MOD * ((m - 1) % MOD) % MOD) % MOD + n % MOD * inv(m % MOD) % MOD * s % MOD) % MOD << endl;
    }

    return 0;
}