题解：P15306 『NFC-OI R1』序列玖

· · 题解

题目传送门

欢迎来博客园食用喵！

题意

题意比较明确了，这里考虑一下操作的本质。

显而易见的是，这题的 a , b 是具有对称性的，也就是说答案一定是一个形如 (ab)^n 的东西。因此考虑从 a 的次数入手。

思路

我们用序列 p_i 来表示第 i 此操作后序列中每一个数的 a 的指数。则 p_0 = \{ 1,0 \} 表示原序列。

我们想起同底数幂的运算法则：同底数幂相乘，底数不变，指数相加。

用序列 d_i 来表示第 i 此操作时新增的数的 a 的指数，则有 d_{i,j} = p_{i-1,j} + p_{i-1,j+1}。容易发现，除了首尾两个数，每个数都加了两次，首尾分别是是 1,0，只加了一次。

分别用 D_i , f_i 表示序列 d_i,p_i 中的数字之和，则：

D_i = 2f_{i - 1} - 1 f_i = D_i + f_{i - 1} f_i = 3f_{i - 1} - 1

这个递推式的边界条件是 f_0 = 1 + 0 =1。

通过注意力或待定系数法可以推出：

f_i - \frac{1}{2} = 3f_{i - 1} - 1 - \frac{1}{2} = 3f_{i - 1} - \frac{3}{2} f_i - \frac{1}{2} = 3(f_{i - 1}-\frac{1}{2}) f_i - \frac{1}{2} = 3^i(f_0-\frac{1}{2}) = \frac{3^i}{2}

因此：

f_k = \frac{3^k + 1}{2}

那么我们所求答案也就是 (ab)^{f_k}。但是由于 f_k 太大了显然不是快速幂可以处理的量级。考虑优化。

看到对大质数取模时想到了费马小定理：当 p 为质数，\gcd(a,p) = 1 时，

a^{p-1} \equiv 1 \pmod{p}

也就是说：

a^{f_k} \equiv a^{f_k \bmod (p-1)} \pmod{p}

这里的 p 就是模数，本题 p = 998244353。

难点又变成了求 f_k \bmod (p-1)。p-1 不是质数，第一想法是用一般的欧拉定理：当 \gcd(a,m) = 1 时，

a^{\varphi(m)} \equiv 1 \pmod{m}

这里 m = p - 1 = 998244352，但如果考虑 \gcd(a,m) = 1 这一条件，貌似就会变得很复杂。更换方向：我们从余数的定义入手：

设 f_k = \frac{3^k + 1}{2} = n \times (p-1) + r，这里 n 是商，r 是余数。我们所求为 r。

化简，得：

3^k + 1 = 2n \times (p - 1) + 2r 3^k = n \times 2(p - 1) + (2r - 1)

注意这里将 2n 的系数提到了模数那里，这是为了去除 n 为偶数的限制条件。

从而 2r - 1 = 3^k \bmod (2p-2)，便可计算了。但是余数 r \in \mathbb{N}，因此验证奇偶性：

## 代码 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll p = 998244353; ll qmi(ll a, ll k, ll m) { ll res = 1ll; while(k) { if(k & 1) res = res * a % m; a = a * a % m; k >>= 1; } return res; } ll solve() { ll a, b, k; cin >> a >> b >> k; ll n = a * b % p; ll r = qmi(3, k, 2 * p - 2); r = (r + 1) / 2; return qmi(n, r, p); } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T; cin >> T; while(T--) cout << solve() << '\n'; return 0; } ``` 感谢阅读喵！