题解：AT_tkppc6_2_a >_<

AT_tkppc6_2_a >_< 题解

题意

把一个 $\{1,2,3,…,n\}$ 的数列 $P$，重新组合，询问满足以下要求的重组序列的数量。
对于每一个 $i$（$2\le i \le n$），满足 $P_i$ 是 $P_{1 \sim i}$ 中最小的值或是最大的值。

思路

考虑最后一位，因为最后一位一定是 $P$ 中最小的值或最大的值，所以一定是 $1,n$。
我们发现，选后 $n - 1$ 个数都有 $2$ 种选择，所以答案是 $2 ^ {n - 1}$。

代码

如果一步一步求时间复杂度是 $O(n)$，会 T。
所以这里用了快速幂。

#include<bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long n;
long long quick_pow(long long x, long long y)
{
	long long ans = 1;
	while(y)
	{
		if(y & 1) 
			ans = (x * ans) % mod;
		x = x * x % mod;
		y >>= 1; 
	}
	return ans;
}
int main()
{
	cin >> n;
	cout << quick_pow(2, n - 1);
    return 0;
}

还是那句话：
$\large \textcolor{red}{\mathbf{题解仅供学习参考使用}}$