求解组合数幂和模 20090327：时间复杂度 O(n) 的 C++ 实现

给定 $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时间复杂度不超过 O(n)，你可以尝试对式子进行推导，使用 C++ 代码实现这一题目，不需要阐述思路内容：/n/nC++ 代码如下：/ncpp/n#include <iostream>/nusing namespace std;/n/nconst int MOD = 20090327;/n/nint main() {/n int n, k;/n cin >> n >> k;/n/n long long ans = 0, fact = 1, powk = 1;/n for (int i = 1; i <= n; ++i) {/n fact = (fact * i) % MOD;/n powk = (powk * k) % MOD;/n ans = (ans + fact * powk) % MOD;/n powk = (powk * powk * powk) % MOD; // 快速幂计算 k^(3^i) /n }/n/n cout << ans << endl;/n return 0;/n}/n