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

· · 题解

题目大意

定义 f(n,m) 为满足如下条件的序列 P_1,P_2,\dots,P_m 的数量：

  1. 序列元素两两不同，均属于集合 \{1,2,\dots,n\}；
  2. 对任意 3\le i\le m，有 [P_i<P_{i-1}]\ne [P_i<P_{i-2}]。

求：

\sum_{m=3}^n f(n,m) \pmod{998244353}

数据范围：3\le n\le 10^6。

题意转化

条件等价于：序列从第三位开始升降严格交替

任意 m 个不同数字，合法摇摆排列方案数为 2^{m-2}。

数学推导

从 n 个数中选 m 个的组合数为 \binom{n}{m}，因此：

f(n,m)=\binom{n}{m}\times 2^{m-2}

答案：

ans=\sum_{m=3}^n \binom{n}{m}\times 2^{m-2}

利用二项式定理化简：

\sum_{m=0}^n \binom{n}{m}2^m=(1+2)^n=3^n

减去 m=0,1,2 三项：

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

最终公式：

ans=\frac{3^n-2n^2-1}{4}\pmod{998244353}

做法

  1. 公式法：直接用通项公式，通过快速幂计算 3^n，再乘上 4 在模 998244353 下的逆元即可；
  2. 组合法：预处理阶乘、排列数、阶乘逆元，枚举 m\in[3,n] 累加贡献。

喜闻乐见的 AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=998244353;
using ll=long long;
ll f[N],p[N],r[N];
ll q(ll a,ll b){ll c=1;for(;b;b>>=1,a=a*a%M)if(b&1)c=c*a%M;return c;}
int main(){
    int n;cin>>n;
    f[0]=1;for(int i=1;i<=n;i++)f[i]=f[i-1]*i%M;
    p[0]=1;for(int i=1;i<=n;i++)p[i]=p[i-1]*(n-i+1)%M;
    r[n]=q(f[n],M-2);for(int i=n;i;i--)r[i-1]=r[i]*i%M;
    ll a=0;
    for(int i=3;i<=n;i++){
        ll t=p[i]*r[i]%M;
        a=(a+t)%M;
    }
    cout<<a*2%M;
}

UP住院了写得不好，见谅一下谢谢