专栏文章

题解：P13280 「CZOI-R4」午夜巡游

MMPLN
P13280题解参与者 7已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@miowobng
此快照首次捕获于
2025/12/03 02:22
3 个月前
此快照最后确认于
2025/12/03 02:22
3 个月前
查看原文
前几天刚在 STAOI 传奇全黑题比赛 中大受震撼，看到这题：排列，跑置换环……
没事这是 div3 的题。

思路

我们可以先计算出最终巡游出来的 x=kx=k 的排列有多少种，设其为 aa，那么显然会剩余 n!−an!-a 种排列 x≠kx\ne k。
由于考虑范围是所有排列，那么对于每个最终巡游出来的 x≠kx\ne k 的排列情况都是对称的。即有 n!−an−1\frac{n!-a}{n-1} 种排列满足最后巡游出某个 x≠kx\ne k。
因此，最终答案就是：
ak+∑1≤i≤n,i≠k(n!−a)in−1ak+\sum_{1\le i\le n,i\ne k}\frac{(n!-a)i}{n-1}
用等差数列求和公式化简一下，即：
ak+(n!−a)(n(n+1)−2k)2n−2ak+\frac{(n!-a)(n(n+1)-2k)}{2n-2}
所以问题就是怎么求 aa。
什么时候跑 mm 次后 x=kx=k？
形象一点，我们发现给一个排列中每个 pxp_x 建一条 x→pxx\rightarrow p_x 的边，其实 xx 就在顺着边在图里不停地跑，而这个图长什么样子？当然就是几个环啦！xx 就从点 kk 出发，在包含 kk 的环里一圈一圈绕，共走 mm 步。 而最终 x=kx=k 就说明 xx 绕回到点 kk 了！这说明这个环的长度是 mm 的因子，可以整除 mm。
所以我们可以用枚举 mm 的因子的方式枚举环的长度 dd，并算出环长为 dd 的时候有多少种可能。换句话说，有多少种排列满足巡游 dd 次后 x=kx=k，且前 d−1d-1 次巡游后都满足 x≠kx\ne k。
不妨找规律：
d=1d=1 时，即 pk=kp_k=k，显然这样的排列数等于剩下的全排列数，即 (n−1)!(n-1)! 种。
d=2d=2 时，即 pk≠kp_k\ne k 的同时 ppk=kp_{p_k}=k，满足前者就是 n!−(n−1)!n!-(n-1)! 个排列，满足后者又是这些情况的 1n−1\frac{1}{n-1}（ppkp_{p_k} 在除了已经确定的 pkp_k 之外的其他数字中选出 kk 的概率），综上为 (n!−(n−1)!)×1n−1=(n−1)!(n!-(n-1)!)\times\frac{1}{n-1}=(n-1)!。
d=3d=3 时，就是 d=2d=2 的情况中 ppkp_{p_k} 在除了已经确定的 pkp_k 之外的其他数字中选出不是 kk 的情况数，再乘上 pppkp_{p_{p_k}} 在除了已经确定的 pk,ppkp_k,p_{p_k} 之外的其他数字中选出 kk 的概率，就是 (n!−(n−1)!)×n−2n−1×1n−2=(n−1)!(n!-(n-1)!)\times\frac{n-2}{n-1}\times\frac{1}{n-2}=(n-1)!。
类似地，d=4d=4 时情况数为 (n!−(n−1)!)×n−2n−1××n−3n−2×1n−3=(n−1)!(n!-(n-1)!)\times\frac{n-2}{n-1}\times\times\frac{n-3}{n-2}\times\frac{1}{n-3}=(n-1)!。
以此类推。
发现无论环长是多少，这样的排列数都是 (n−1)!(n-1)!。
不严谨的理解：d=1d=1 的时候是 (n−1)!(n-1)!，一般来说这个情况数随着 dd 增大要么减少要么增加要么不变，而发现 dd 取值有 nn 种情况，(n−1)!×n=n!(n-1)!\times n=n! 即全部情况，那么我猜他就是不变。
综上，
a=cnt×(n−1)!a=cnt\times(n-1)!
其中 cntcnt 为 mm 的正整数因子中 ≤n\le n 的数量。
再放一遍答案：
ak+(n!−cnt×(n−1)!)(n(n+1)−2k)2n−2ak+\frac{(n!-cnt\times(n-1)!)(n(n+1)-2k)}{2n-2}
所以我们预处理阶乘，按照上述式子算就可以了。

参考代码

时间复杂度 O(V+Tn)O(V+T\sqrt{n})，VV 为 nn 取值上限。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
int T, n, m, k, jc[10000010];
signed main() {
    jc[0] = 1;
    for (int i = 1; i <= 10000000; i++)
        jc[i] = jc[i - 1] * i % MOD;
    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        if (m == 0) cout << jc[n] * k % MOD << endl;
        else {
            int cnt = 0;
            for (int i = 1; i * i <= m; i++) {
                if (m % i != 0) continue;
                if (i <= n) cnt++;
                if (i != m / i && m / i <= n) cnt++;
            }
            int othersum = ((n + 1) * n / 2 % MOD - k + MOD) % MOD;
            int ans =
                k * jc[n - 1] % MOD * cnt % MOD +
                othersum * jc[n - 2] % MOD * (n - cnt) % MOD;
            cout << ans % MOD << endl;
        }
    }
    return 0;
}
如果你有任何疑问或者觉得讲得不好的地方，欢迎留言！
如果没有，点赞。

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...