求解数列和的模运算 - 优化算法及 C++ 代码实现

求解数列和的模运算 - 优化算法及 C++ 代码实现给定正整数 $n$ 和 $k$，设 $a_i=27/times /frac{3^i-1}{2}$，求解以下数列和的模运算结果：$$/sum/limits_{i=1}^{n}{i!}/times {k^{a_i}} /pmod {20090327}$$### 算法思路1. 化简通项公式: 首先根据 $a_i$ 的定义，我们可以化简出 $a_i$ 的通项公式为: $$a_i=27/times /frac{3^i-1}{2}=13/times 3^i-13$$2. 快速幂计算: 考虑 $k^{a_i}$，我们可以将 $a_i$ 分解为 $a_i=13/times 3^{i-1}/times 3-13$。 然后利用快速幂和一些小技巧，可以快速计算出 $k^{a_i}$。 具体来说，我们可以预处理出 $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$。3. 预处理和累加: 最终的答案为 $/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}$ 一起累加即可。### C++ 代码实现cpp#include #include using namespace std;const int MOD = 20090327;int k, n;int a[100005], fac[100005], pow3[100005], powk[100005];int quickPow(int a, int b) { int res = 1; while (b) { if (b & 1) res = 1LL * res * a % MOD; a = 1LL * a * a % MOD; b >>= 1; } return res;}int main() { scanf('%d%d', &n, &k); pow3[0] = 1, powk[0] = 1; for (int i = 1; i <= n; ++i) { fac[i] = 1LL * fac[i - 1] * i % MOD; pow3[i] = 1LL * pow3[i - 1] * 3 % MOD; powk[i] = 1LL * powk[i - 1] * k % MOD; a[i] = 13 * pow3[i - 1] * 3 - 13; } int ans = 0; for (int i = 1; i <= n; ++i) { int tmp = 1LL * fac[i] * powk[a[i]] % MOD; ans = (ans + tmp) % MOD; } printf('%d/n', ans); return 0