题解 AT_tkppc6_2_a >_<

· · 题解

Description

问所有长度为 n 的排列中，有多少排列 P 满足 \forall i\in[2,n]，i 前面的数全都比 P_i 小或大。

Solution

其他题解已经给出了答案：2^{n-1}，但是没人证过。这里给出证明方法。

考虑构造满足条件排列的过程，首先 P_1 可以随便选取，而 P_2 必须满足 |P_1-P_2|=1，否则值在 P_1 和 P_2 间的数在后面选取时会比其中一个大，比另一个小。

类似地，当我们已经确定前 i 个数的取值时，这 i 个数一定能重排成值域上连续的一段 [l,r](r-l+1=i)，且第 i+1 个数必须取 l-1 或 r+1。所以构造排列的过程其实就是扩展值域的过程。

回到排列的第一个数，当取 P_1=a 时，后面的构造过程中有 n-1 次扩展值域，其中有 a-1 次取了 l-1。易得若扩展值域的操作序列不同，则最终得到的排列不同。故排列数量等于操作序列数量，即 \displaystyle \binom{n-1}{a-1}。

所有满足条件的排列数共有 \displaystyle \sum_{i=1}^n \binom{n-1}{i-1}=\sum_{i=1}^{n-1} \binom{n-1}{i}=2^{n-1} 个。

Code

给出一种容易记忆的快速幂写法。

const int N=100005,mod=998244353;
ll x;
int fast_pow(int d,ll z){
    int ans=1;
    while(z){
        if(z&1)ans=(1ll*d*ans)%mod;
        d=(1ll*d*d)%mod;
        z>>=1;
    }
    return ans;
}
void solve(){
    read(x);
    print(fast_pow(2,x-1));
}