题解：P16351 「Gensokyo OI Round 1」秘神之钥 / ARIS0_0 - 17

小屹0_0 · 2026-04-26 17:10:40 · 题解

前言

嘟嘟嘟奋战一整场切了 T3 太好力。

有个大佬干到了一个 O(n) 预处理，O(1) 查询的模数固定做法，但是我没有，可是我也没看懂第一篇题解在说什么。

思路

做法很多。

首先我们定义一个操作序列，由每次操作时左边的数的原编号，当前数的编号，右边的数的编号这个三元组构成。

注意是原编号不是数！

我们用一个 n=4 和 n=5 的情况说明一下。

操作过程：(a_1,a_2,a_3,a_4) \rightarrow (a_1,a_4,a_3,a_2) \rightarrow (a_3,a_4,a_1,a_2) \rightarrow (a_3,a_2,a_1,a_4) \rightarrow (a_1,a_2,a_3,a_4)。

操作序列：\{ (4,1,2),(1,4,3),(4,1,2),(1,4,3) \}。

但是注意我们是不可重集合，所以操作序列：\{ (4,1,2),(1,4,3) \}。

操作过程：(a_1,a_2,a_3,a_4,a_5) \rightarrow (a_1,a_5,a_3,a_4,a_2) \rightarrow (a_3,a_5,a_1,a_4,a_2) \rightarrow (a_3,a_4,a_1,a_5,a_2) \rightarrow (a_3,a_4,a_2,a_5,a_1) \rightarrow (a_5,a_4,a_2,a_3,a_1)。

操作序列：\{ (5,1,2),(1,5,3),(5,1,4),(1,5,2),(5,1,3) \}。

然后我们发现每一次操作以 1 或 n 为中心展开，左右两侧有另一个数。

接下来大力推式子和猜结论。

考虑到我们无论如何，最终的大小关系和 (a_1, a_n) 的有关。

你发现题目中的限制是至少一个，然后总方案是固定的 n!。

于是直接正难则反，求一个所有条件都不满足的方案数。

正难则反过后的限制很强，不妨设 a_1 < a_n，对于每个数都有限制。

你发现对于偶数每个数的限制要么比 a_n 小，要么比 a_1 大。

不妨设限制是大于 a_1 的有 x 个，小于 a_n 的有 y 个，满足 x+y=n-2。

那么你的方案数是 (C_n^{x+1} - 1) \times x! \times y!，注意这里要减 1，有一种不合法情况。

大体意义是，你从 n 个数中选出 x+1 哥，分配给 a_1，和现实是大于 a_1 的所有数，然后减去一种这些书占掉了最大的 x + 1 个坑位的情况，然后对于每一个选择，大于 a_1 的数互相没有限制，乘上 x!，同理，也要乘上 y!。

当 n 是奇数的时候，你发现有的数字可能重复的出现在大于 a_1 和小于 a_n 中间。

做到这里卡了我很久，所以这里大概是一个重点，我推了接近一整场才发现的规律。

这里不要去想那个 O(1) 的做法了，虽然可行但是过于浪费时间。

设 x 是限制中含有但不限于大于 a_1 的数的个数，y 表示限制是大于 a_1 且小于 a_n 的数的个数，z 是限制中含有但不限于小于 a_n 得数的个数。

我们考虑枚举 i 表示恰好有 i 个，原本下限值仅仅是大于 a_1 的，最终也小于 a_n 了，那么 i 的范围是 0 \sim x - y。

设 t = x - y - i，表示还有 t 个事确实大于 a_n 的，这里先把式子给出来：C_{n-t-1}^{y+i+1} \times C_{y+i}^{y} \times y! \times (x-y)! \times (n - x - 2)!。

含义是你发现你比 a_n 大的 t 个数和 a_n 他们取的一定是连续的最大的 t + 1 个数，所以你只需要在 n - (t + 1) 中取你限制是在 a_1 \sim a_n 中和没有小于 a_n 限制但是小于 a_n 的数 和 a_1，也就是取 y+i+1 个。

接下来你在你取出来的除了 a_1（注意，这里 a_1 肯定是你要选的数中最小的一个，所以但凡你有这些数的集合，a_1 就是固定的那个集合中的最小值）以外的 y+i 个数中选出 y 个为本身就有两个限制的数。

最后，这 y 个数可以重排，只有大于 a_1 但是没有小于 a_n 限制的 x - y 个数可以重排，其他的 n-x-2=y-z 个数也可以重排，所以乘上了三个阶乘。

这样代码就好写了。

code

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second
const int N = 1e6 + 5;

namespace ARIS0_0{
    int n, mod;
    int p[N], fac[N], inv[N];
    bool vis[N], vis1[N], vis2[N];

    int qpow(int a, int b){
        int res = 1;
        while (b){
            if (b & 1) res = 1ll * res * a % mod;
            a = 1ll * a * a % mod, b >>= 1;
        }
        return res;
    }
    int C(int n, int m){
        if (n < m) return 0;
        return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
    }
    void init(){
    }
    void solve(){
        cin >> n >> mod;

        if (n % 2 == 0){
            for (int i = 1; i <= n; i ++ ) vis[i] = 0;
            fac[0] = 1;
            for (int i = 1; i <= n; i ++ ) fac[i] = 1ll * fac[i - 1] * i % mod;
            inv[n] = qpow(fac[n], mod - 2);
            for (int i = n - 1; i >= 0; i -- ) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
            int all = fac[n];

            for (int i = 1; i <= n; i ++ ) p[i] = i;
            int x = 0, y = 0;
            for (int i = 1; i <= n; i ++ ){
                int l = (i == 1 ? n : i - 1);
                int r = (i == n ? 1 : i + 1);
                if (p[i] == 1){
                    if (p[l] == n) swap(l, r);
                    if (!vis[p[l]]) x ++, vis[p[l]] = 1;
                }
                else{
                    if (p[r] == 1) swap(l, r);
                    if (!vis[p[r]]) y ++, vis[p[r]] = 1;
                }
                swap(p[l], p[r]);
            }

            int tmp = 2ll * ((C(n, x + 1) + mod - 1) % mod) % mod * fac[x] % mod * fac[y] % mod;
            cout << ((all - tmp) % mod + mod) % mod << '\n';
        }
        else{
            for (int i = 1; i <= n; i ++ ) vis1[i] = vis2[i] = 0;
            fac[0] = 1;
            for (int i = 1; i <= n; i ++ ) fac[i] = 1ll * fac[i - 1] * i % mod;
            inv[n] = qpow(fac[n], mod - 2);
            for (int i = n - 1; i >= 0; i -- ) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
            int all = fac[n];

            for (int i = 1; i <= n; i ++ ) p[i] = i;
            int x = 0, y = 0, z = 0;
            for (int i = 1; i <= n; i ++ ){
                int l = (i == 1 ? n : i - 1);
                int r = (i == n ? 1 : i + 1);
                if (p[i] == 1){
                    if (p[l] == n) swap(l, r);
                    vis1[p[l]] = 1;
                }
                else{
                    if (p[r] == 1) swap(l, r);
                    vis2[p[r]] = 1;
                }
                swap(p[l], p[r]);
            }
            for (int i = 1; i <= n; i ++ ){
                if (vis1[i] && vis2[i]) y ++;
                if (vis1[i]) x ++;
                if (vis2[i]) z ++;
            }

            int tmp = 0;
            for (int i = 0; i <= x - y; i ++ ){
                int t = x - y - i;
                tmp = (tmp + 1ll * C(n - t - 1, y + i + 1) * C(y + i, y) % mod * fac[y] % mod * fac[x - y] % mod * fac[n - x - 2] % mod) % mod;
            }
            tmp = 2ll * tmp % mod;
            cout << ((all - tmp) % mod + mod) % mod << '\n';
        }
    }
    void single(){ init(), solve(); }
    void multi(){ init(); int T; cin >> T; while (T -- ) solve(); }
    void idmulti(){ init(); int id, T; cin >> id >> T; while (T -- ) solve(); }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ARIS0_0::multi();
}
// 可能南方的阳光，照着北方的风。
// 可能时光被吹走，从此无影无踪。
// 跑题了，没关系。祝好
// ARIS0_0 - 17