AT_tkppc6_2_a题解

· · 题解

题意

有一个数列 P 为 (1,2,\dots,n)，求出所有打乱后的数列满足以下条件的数量，对 998244353 取膜。

对于所有 i（2≤i≤N），以下任一项成立。

此题就是让我们求 2^{n-1}\bmod 998244353 的值。

证明：

首先，考虑边界情况，当 N=1 时，只有一个数 1，没有其他数列满足条件，因此答案是 0。

然后，假设对于一个长度为 N-1 的数列，满足条件的数量是 2^{N-1}-1。我们来证明对于长度为 N 的数列，满足条件的数量是 2^{N-1}。

对于长度为 N 的数列，最后一个数可以是任意数字，有 N 种选择。然后考虑倒数第二个数，它必须满足两个条件:

不能比最后一个数大。

对于倒数第三个数及之前的所有数，都不能比倒数第二个数大。

根据第一个条件，倒数第二个数可以是 1,2,3,\cdot\cdot\cdot N-1 共 N-1 种选择；根据第二个条件，倒数第二个数的选择要受到前面所有数的限制。

假设倒数第二个数选择了 k，则前面的 k-1 个数必须按照升序排列，从 1\sim k-1。

对于剩下的 N-2 个位置，它们的选择是与问题的规模 N-1 相同的子问题。根据归纳假设，满足条件的数量是 2^{N-1}-1。

因此，对于长度为 N 的数列，满足条件的数量是 (N-1)\times (2^{N-1}-1)。

综上所述，我们可以推导出对于任意的 N，满足条件的数列数量是 (N-1) \times (2^{N-1}-1) = 2^{N-1}。

但是此题的数据太恐怖，2\le n\le 10^{18}，用普通方法定超时。

那该怎么办呢？ 这得使用快速幂。

今天我就跟你们讲一下快速幂吧！

快速幂算法是一种高效计算指数幂的算法，其基本思路是将指数进行二进制拆分，然后通过连续平方和积的方式来计算幂。

具体来说，设待计算的幂为 x^n，根据二进制拆分，n 可以表示为二进制形式的多个位数相加，例如 n = 9 可以表示为 2^3 + 2^0。

那么，x^n 可以转化为 x^{2^3}\times x^{2^0}。

在计算时，我们可以利用以下性质：

若 m 为偶数，则 x^m = (x^{m/2})^2。

若 m 为奇数，则 x^m = x\times (x^{(m-1)/2})^2。

根据这个性质，我们可以使用迭代的方式计算出 x^n。

以下是一个使用快速幂算法计算 x^n 的示例代码：

long long fastPower(long long x, long long n) {
    long long result = 1;
    while (n > 0) {
        if (n % 2 == 1) {  // 当当前位为 1 时，将该位的贡献乘到结果中
            result = result * x % MOD;
        }
        x = x * x % MOD;  // 将 x 的平方作为下一位的贡献
        n /= 2;  // n 右移一位，相当于将二进制位向右移动一位
    }
    return result;
}

通过使用快速幂算法，我们可以大大减少乘法的次数，从而提高计算效率。

完整代码就不放出来了。