题解：P16450 [XJTUPC 2026] 但是什么也不会改变 3

Jason20090916 · 2026-05-10 21:51:59 · 题解

题意

定义 f(n,m) 为从 \{1,2,\cdots,n\} 里选出 m 个数进行全排列后，对于任意的 i（3\le i\le m), 满足 P_i 在 [\min(P_{i - 1}, P_{i - 2}), \max(P_{i - 1}, P_{i - 2})] 之间的排列的数量。
给定一个正整数 n，求 \sum_{i=3}^n f(n,i)。

思路

如果已经确定了 P_1 和 P_2，那么这个排列是唯一确定的，且 P_1 和 P_2 是选出的 m 个数的最大值和最小值。
因为从 n 个数里面选 m 个的方案数为 \dbinom{n}{m}，且我们可以选择 P_1 为最大值还是最小值，那么 f(n,m) = 2\dbinom{n}{m}，原问题变为求 \sum_{i=3}^n 2\dbinom{n}{i}。

::::success[Code]

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;

const int MAXN = 1e6 + 9, MOD = 998244353;
int n, p[MAXN];
void init() {
    p[0] = 1;
    for(int i = 1; i <= n; i++) p[i] = p[i - 1] * i % MOD;
}
int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
}
int C(int n, int m) {
    return p[n] * qpow(p[m] * p[n - m] % MOD, MOD - 2) % MOD;
}

void solve() {
    cin >> n;
    init();
    int ans = qpow(2, n);
    ans = (ans - 1 + MOD) % MOD;
    ans = (ans - C(n, 1) + MOD) % MOD;
    ans = (ans - C(n, 2) + MOD) % MOD;
    ans = ans * 2 % MOD;
    cout << ans;
    return;
}

signed main() {
    solve();
    return 0;
}

::::