C++ 实现求解 $/sum/limits_{i=1}^{n}{i!}/times {k^{a_i}} /pmod {20090327}$，时间复杂度 O(n)

C++ 实现求解 $/sum/limits_{i=1}^{n}{i!}/times {k^{a_i}} /pmod {20090327}$，时间复杂度 O(n)/n/n给定 $n$ 和 $k$，设 $a_i=27/times /frac{3^i-1}{2}$，求 $/sum/limits_{i=1}^{n}{i!}/times {k^{a_i}} /pmod {20090327}$。/n/n推导/n/n首先，我们可以将 $a_i$ 展开为：/n/n$$a_i=27/times /frac{3^i-1}{2}=13/times 3^i-13/times 2^{i-1}$$ /n/n然后我们可以将 $i!$ 拆分为 $i/times (i-1)!$，即：/n/n$$/sum_{i=1}^{n} i!/times k^{a_i}=/sum_{i=1}^{n} i/times (i-1)!/times k^{13/times 3^i-13/times 2^{i-1}}$$ /n/n接着，我们考虑对于不同的 $i$，$13/times 3^i$ 和 $13/times 2^{i-1}$ 的值是相差很大的，因此我们可以先预处理出 $/{k^{13/times 3^i}/}$ 和 $/{k^{13/times 2^{i-1}}/}$，然后再对于每个 $i$ 进行计算，这样时间复杂度就可以做到 $O(n)$。/n/n代码实现/n/ncpp/n#include <iostream>/nusing namespace std;/n/nconst int MOD = 20090327;/n/nlong long pow_mod(long long a, long long b) {/n long long res = 1;/n while (b) {/n if (b & 1) {/n res = (res * a) % MOD;/n }/n a = (a * a) % MOD;/n b >>= 1;/n }/n return res;/n}/n/nint main() {/n int n, k;/n cin >> n >> k;/n /n long long fac[n + 1]; // 存储阶乘/n fac[0] = 1;/n for (int i = 1; i <= n; ++i) {/n fac[i] = (fac[i - 1] * i) % MOD;/n }/n /n long long p3[n + 1], p2[n + 1]; // 预处理 k 的幂次/n p3[0] = 1;/n p2[0] = 1;/n for (int i = 1; i <= n; ++i) {/n p3[i] = (p3[i - 1] * pow_mod(k, 13 * 3)) % MOD;/n p2[i] = (p2[i - 1] * pow_mod(k, 13 * 2)) % MOD;/n }/n /n long long sum = 0;/n for (int i = 1; i <= n; ++i) {/n sum = (sum + (i * fac[i - 1] % MOD * p3[i] % MOD * pow_mod(p2[i], MOD - 2)) % MOD) % MOD;/n }/n /n cout << sum << endl;/n return 0;/n}/n/n/n代码解释/n/n* pow_mod(a, b) 函数用于计算 $a^b /pmod {MOD}$。/n* fac[i] 数组存储 $i!$ 的值。/n* p3[i] 数组存储 $k^{13/times 3^i}$ 的值。/n* p2[i] 数组存储 $k^{13/times 2^{i-1}}$ 的值。/n* 最后，使用循环计算 $/sum/limits_{i=1}^{n}{i!}/times {k^{a_i}} /pmod {20090327}$ 的值。/n/n时间复杂度分析/n/n预处理阶乘和 $k$ 的幂次需要 $O(n)$ 时间，计算 $/sum/limits_{i=1}^{n}{i!}/times {k^{a_i}} /pmod {20090327}$ 也需要 $O(n)$ 时间，因此总的时间复杂度为 $O(n)$。/n/n注意/n/n* 代码中的取模操作需要仔细处理，确保结果始终在模数范围内。/n* 可以根据需要修改代码中的模数和变量类型。/n/n总结/n/n通过对式子的推导和预处理，我们可以使用 C++ 代码高效地求解数学问题 $/sum/limits_{i=1}^{n}{i!}/times {k^{a_i}} /pmod {20090327}$，并将时间复杂度优化到 $O(n)$。/n