求解数列和的模运算 - 优化算法及 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++ 代码实现这一题目内容：首先根据 $a_i$ 的定义，我们可以化简出 $a_i$ 的通项公式为 $a_i = 27 //times //frac{3^i - 1}{2} = 13 //times 3^i - 13$。/n/n考虑 $k^{a_i}$，我们可以将 $a_i$ 分解为 $a_i = 13 //times 3^{i-1} //times 3 - 13$，然后利用快速幂和一些小技巧，可以将 $k^{a_i}$ 快速计算出来。/n/n具体来说，我们可以预处理出 $k^1, k^3, k^9, //cdots, k^{3^{n-1}}$，然后将 $a_i$ 写成 3 进制，例如 $a_i = 13 //times 3^3 + 2 //times 3^2 + 1 //times 3^1 + 0 //times 3^0$，然后根据 $k^{x //times y} = (k^x)^y$，可以用快速幂 $O(//log_2 a_i)$ 的时间计算出 $k^{a_i} = (k^{3^3})^{13} //times (k^{3^2})^2 //times (k^{3^1})^1 //times (k^{3^0})^0$。/n/n最终的答案为 $/sum/limits_{i=1}^{n}{i!} //times {k^{a_i}} = /sum/limits_{i=1}^{n}{i!} //times {k^{13 //times 3^{i-1} //times 3 - 13}}$。我们可以用 $O(n)$ 的时间将 $i!$ 和 $13 //times 3^{i-1} //times 3 - 13$ 预处理出来，然后将它们与 $k^{13 //times 3^{i-1} //times 3 - 13}$ 一起累加即可。/n/n最终的时间复杂度为 $O(n)$，可以通过本题。/n/n参考代码：/ncpp/n#include <iostream>/nusing namespace std;/n/nconst int MOD = 20090327;/n/nlong long quick_pow(long long base, long long exp) {/n long long res = 1;/n while (exp) {/n if (exp & 1) {/n res = (res * base) % MOD;/n }/n base = (base * base) % MOD;/n exp >>= 1;/n }/n return res;/n}/n/nint main() {/n long long 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 pows[n];/n pows[0] = quick_pow(k, 1);/n for (int i = 1; i < n; ++i) {/n pows[i] = (pows[i - 1] * pows[i - 1] * pows[i - 1]) % MOD;/n }/n /n long long ans = 0;/n for (int i = 1; i <= n; ++i) {/n long long a = (13 * quick_pow(3, i) - 13) % MOD;/n long long term = fac[i] * quick_pow(pows[i - 1], 13) % MOD;/n ans = (ans + term) % MOD;/n }/n /n cout << ans << endl;/n return 0;/n}/n