题解：AT_tkppc6_2_a >_<

· · 题解

题目链接

AT_tkppc6_2_a

思路

其实这道题找到规律后会很简单。

我先自己造了几组数据，并手搓了一会，得出了其结果，如下表：

输入 输出
2 2
3 4
4 8
5 16
6 32

如果我们仔细观察这些数据，就会发现这些数都是不断乘 2，而这些数都是 2 的整数次方。

再分析一下，把前文中输出拆解如下：

原输出 拆解后的结果
2 2^1
4 2^2
8 2^3
16 2^4
32 2^5

我们发现：所有拆解后的结果的指数都是 n-1，那么我们就可以得出公式：

ans=2^{n-1}

证明：从后往前推，每一位都只能选剩下的最大值或最小值。第一个数有且仅有一种选法。 这样每次二选一都会在前一次选完后的可能性乘 2，总共 n-1 个 2 相乘，化简后和前文相符。证毕。

有了这个，我们就可以做题了，结果取模 998244353。

讲得自认为比较详细，代码就不给了。有不会的欢迎问我。管理求过。