C++ 实现求解数列和模 20090327 的问题

给定 $n$ 和 $k$，设 $a_i=27 \times \frac{3^i-1}{2}$，求 $\sum\limits_{i=1}^{n}{i!} \times {k^{a_i}} \pmod {20090327}$。

使用 C++ 实现这一题目，时间复杂度不超过 O(n)，你可以尝试对式子进行推导。

首先，将 $a_i$ 展开，得到

$$a_i=27 \times \frac{3^i-1}{2}=13 \times 3^i-13 \times 2^{i-1}$$

我们可以发现，当 $i$ 增加时，$a_i$ 以 $3$ 为底的指数会增加 $1$，以 $2$ 为底的指数会减少 $1$，因此我们可以考虑使用差分来处理这个指数。

具体地，设 $b_i=k^{a_i}$，$c_i=b_{i+1}-b_i$，那么有

$$c_i=k^{13 \times 3^{i+1}-13 \times 2^i}-k^{13 \times 3^i-13 \times 2^{i-1}}=k^{13 \times 3^i(3-1)-13 \times 2^{i-1}(2+1)}(k^{13 \times 3^i}-k^{13 \times 2^{i-1}})$$

注意到 $13$ 是质数，因此可以使用费马小定理来求逆元，即

$$k^{20090326} \equiv 1 \pmod {20090327}$$

$$k^{-1} \equiv k^{20090326-1} \pmod{20090327}$$

于是我们可以将 $c_i$ 中的 $k^{13 \times 3^i}$ 和 $k^{13 \times 2^{i-1}}$ 换成它们的逆元，即

$$c_i=k^{13 \times 3^i(3-1)-13 \times 2^{i-1}(2+1)} \times \frac{k^{20090326-13 \times 3^i}-k^{20090326-13 \times 2^{i-1}}}{k^{20090326}}$$

注意到 $13 \times 3^i$ 和 $13 \times 2^{i-1}$ 都是小于 $20090326$ 的，因此可以预处理出 $k^{13 \times 3^i}$ 和 $k^{13 \times 2^{i-1}}$ 的逆元，剩下的就是一个前缀和，时间复杂度为 $O(n)$。

最后，需要注意的是，当 $i=1$ 时，$a_1=13$，因此需要单独处理。

以下是用 C++ 实现的代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int MOD = 20090327;

long long quick_pow(long long base, long long exp) {
    long long ans = 1;
    while (exp) {
        if (exp & 1) ans = ans * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return ans;
}

long long inv(long long x) {
    return quick_pow(x, MOD - 2);
}

int main() {
    long long n, k;
    cin >> n >> k;

    long long b[n + 1], c[n + 1];
    b[1] = quick_pow(k, 13);
    for (int i = 2; i <= n; i++) {
        b[i] = b[i - 1] * quick_pow(k, 26 * quick_pow(3, i - 1)) % MOD;
    }
    
    long long k3[n + 1], k2[n + 1];
    k3[0] = 1;
    k2[0] = 1;
    for (int i = 1; i <= n; i++) {
        k3[i] = k3[i - 1] * quick_pow(k, 13 * quick_pow(3, i)) % MOD;
        k2[i] = k2[i - 1] * quick_pow(k, 13 * quick_pow(2, i)) % MOD;
    }
    
    for (int i = 1; i <= n; i++) {
        c[i] = quick_pow(k, 26 * quick_pow(3, i) - 39 * quick_pow(2, i - 1)) % MOD * (inv(k3[i]) - inv(k2[i]) + MOD) % MOD;
    }

    long long ans = b[1];
    for (int i = 2; i <= n; i++) {
        ans = (ans + c[i - 1] * i % MOD) % MOD;
    }
    
    long long fac = 1;
    for (int i = 2; i <= n; i++) {
        fac = fac * i % MOD;
    }

    cout << (ans * fac % MOD) << endl;
    return 0;
}

这段代码实现了上述推导的步骤，并使用了快速幂和费马小定理来计算逆元，时间复杂度为 $O(n)$。