C++ 代码实现求解组合数和幂的模运算 - 优化时间复杂度至O(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时间复杂度不超过O(n)，你可以尝试对式子进行推导，使用C++代码实现这一题目，不需要阐述思路内容：/n代码如下：/ncpp/n#include <iostream>/n#include <algorithm>/n#define MOD 20090327/nusing namespace std;/n/nlong long fac[1000005]; // 存储阶乘/nlong long k_pow[1000005]; // 存储k的幂/n/nint main() {/n int n, k;/n cin >> n >> k;/n fac[0] = 1;/n for (int i = 1; i <= n; i++) {/n fac[i] = (fac[i - 1] * i) % MOD;/n }/n k_pow[0] = 1;/n long long a = 27 * (3 - 1) / 2;/n k_pow[1] = (k * k * k) % MOD;/n for (int i = 2; i <= n; i++) {/n a = 27 * (pow(3, i) - 1) / 2;/n k_pow[i] = (k_pow[i - 1] * k_pow[1]) % MOD;/n }/n long long sum = 0;/n for (int i = 1; i <= n; i++) {/n sum = (sum + fac[i] * k_pow[i]) % MOD;/n }/n cout << sum << endl;/n return 0;/n}/n/n