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

· · 题解

社贡咋掉了，水篇题解。

哦不对现在是不是周日晚上啊。/kel

不难发现 [P_i<P_{i-1}]\neq[P_i<P_{i-2}] 这个条件等价于 \min(P_{i-1},P_{i-2})<P_i<\max(P_{i-1},P_{i-2})。

这些 P_i 之间又没啥限制，不太好搞。我们先来考虑对于一个 \{Q_1,Q_2,\dots,Q_k\} \subseteq \{1,2,\dots,n\} 且 Q_1<Q_2<\dots<Q_k，有多少种其排列方式可以满足题设中的第二条条件。

从我们转化得到的这个条件可以看出，对于 Q 的一个排列 Q'，若其满足第二个条件，则一定有 \max(Q'_1,Q'_2)>Q'_3>Q'_4>Q'_5>\dots>Q'_n>\min(Q'_1,Q'_2)，证明的话你可以放到数轴上考虑一下，应该是比较清楚的。于是你会发现可变的地方就只有 Q'_1 和 Q'_2 可以交换，因此对于一个 Q 其可行的排列只有 2!=2 种。

现在我们只需要考虑计算 Q 的数量。如果没有 k \ge 3 的限制，那么 1 \sim n 中每个数都是选或不选（当然，不能一个都不选），总个数就是 2^n-1；现在有了这个限制，只需把 k=1 和 k=2 的情况减掉。

故最终答案为

2 \times (2^n-1-n-\dfrac{n(n-1)}{2})

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
signed main() {
    int n; cin >> n;
    int ans = 1;
    for(int i = 1;i <= n;i++)
        ans = (ans * 2) % mod;
    ans = (ans - 1 + mod) % mod;
    ans = (ans - n + mod) % mod;
    ans = (ans - (n * (n - 1) / 2) % mod + mod) % mod;
    ans = (ans * 2) % mod; cout << ans << endl;
    return 0;
}