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

· · 题解

定义 f(n,m) 是从 \{1,...,n\} 中选出 m 个不同数构成排列，且每个从第 3 位开始的数都在它前两个数的数值之间内的合法排列总数。

统计满足特定局部大小关系约束的排列子序列数量之和。分析条件，发现每个新加入的元素必须在前两个元素之间，且不能是三个数中的最大值或最小值。

对于任意长度 m（m \ge 2），集合 \{1,2,...,m\} 中满足条件的排列数恒为 2。这两种排列是从最小值开始交替插入最大值和次小值还有从最大值开始交替插入最小值和次大值。

所以，从 n 个数中选 m 个数的合法方案数为 2 \times \binom n m。

最终答案为 \sum_{m = 3}^{n} \times f(n,m) = 2 \times \sum_{m = 3}^{n} \times \binom n m。根据二项式恒等式 \sum_{i = 0}^{n} \times \binom n i = 2^n 得：

2 \times \sum_{m = 3}^{n} \times \binom n m = 2 \times (2^n - 1 - n - \frac{n \times (n - 1)}{2})

最后取模得：

2 \times (2^n - 1 - n - \frac{n \times (n - 1)}{2}) \bmod{998244353}

:::success[AC Code]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;
int n;
int c0=1;
int sum=(MOD+1)/2;
int mod_pow(int a,int e) {
    int res=1;
    a%=MOD;
    while(e>0) {
        if(e%2==1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        e/=2;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    int pow2_n=mod_pow(2,n);
    int c1=n%MOD;
    int m=n%MOD;
    int cnt=(n-1)%MOD;
    int c2=(m*cnt)%MOD;
    c2=(c2*sum)%MOD;
    int s=(c0+c1+c2)%MOD;
    int v=(pow2_n-s+MOD)%MOD;
    cout<<(2*v)%MOD<<endl;
    exit(0);
}

:::