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

· · 题解

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

解题思路

条件 [P_i<P_{i-1}]=[P_i<P_{i-2}] 意味着 P_i 必须比前两个都小或都大。前两个数有 n(n-1) 种选法。从第 3 个数开始，第 i 步可选数为 n-2(i-2)。因此：

f(n,m)=n(n-1)\prod_{j=1}^{m-2}(n-2j)

求和化简得：

\sum_{m=3}^n f(n,m)=2^{n+1}-2-2n-n(n-1)

::::success[证明] 第 i 步时，最后两个数设为 x<y。已选过 i-3 个数，它们要么小于 x，要么在 x,y 之间，要么大于 y。
比 x 小的未选数有 (x-1)-(i-3) 个，比 y 大的未选数有 (n-y)-(i-3) 个。
两者相加得 n-2-2(i-3)=n-2(i-2)，与 x,y 无关。x>y 时同理。

因此 f(n,m)=n(n-1)\prod_{i=3}^m (n-2(i-2))。
求和化简得 2^{n+1}-2-2n-n(n-1)。 ::::

复杂度分析

时间复杂度：O(\log n)。 空间复杂度：O(1)。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353;

int ksm(int a,int b){
    int r=1;
    while(b){
        if(b&1) r=r*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return r;
}

signed main(){
    int n;
    scanf("%lld",&n);
    int ans=ksm(2,n+1);
    ans=(ans-2+MOD)%MOD;
    ans=(ans-2*n%MOD+MOD)%MOD;
    ans=(ans-n*(n-1)%MOD+MOD)%MOD;
    printf("%lld\n",ans);
    return 0;
}