求解模运算和阶乘之和：快速算法与代码实现

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

根据指数循环节的性质，$a_i$ 的后 $6$ 位是有循环节的，长度为 $6\times 2^{i-2}$。因此，可以预处理出 $a_i$ 的后 $6$ 位的循环节，然后按照循环节来计算。

具体来说，设 $t_i=3^i\pmod {1000000}$，$b_i=a_i\pmod{2^{i-2}}$，$c_i=k^{b_i}\pmod{20090327}$，则 $$\sum_{i=1}^{n}i!\times k^{a_i}\equiv\sum_{i=1}^{n}i!\times c_i\times t_{a_i\div 2^{i-2}}\pmod{20090327}$$

预处理 $t$ 数组和 $c$ 数组的时间复杂度都是 $O(2^n)$ 的，但是由于 $n\le 10^6$，因此是可行的。

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

const int MOD = 20090327;

int t[1000001], c[1000001];

int main() {
    int n, k;
    cin >> n >> k;
    t[0] = 1;
    for (int i = 1; i <= n; i++) {
        t[i] = (t[i - 1] * 3) % 1000000;
    }
    c[0] = 1;
    for (int i = 1; i <= n; i++) {
        c[i] = (c[i - 1] * 1LL * k) % MOD;
    }
    long long ans = 0, fac = 1;
    for (int i = 1; i <= n; i++) {
        ans = (ans + fac * c[i] * t[i / (1LL << (i - 2))]) % MOD;
        fac = (fac * 1LL * i) % MOD;
    }
    cout << ans << endl;
    return 0;
}