P8110 [Cnoi2021] 矩阵

难度	算法s	日期	题目链接
普及+/提高	快速幂	2025-09-24	https://luogu.com.cn/problem/

看似矩阵快速幂，实则推式子 + 普通快速幂。

题意简述

给定两个长度为 \(n\) 的数列 \(\{a_1,a_2,\dots,a_n\},\{b_1,b_2,\dots,b_n\}\)，\(n\times n\) 的矩阵 \(A\) 满足 \(A_{ij}=a_i\times b_j\)。

求：\((\sum_{i=1}^n\sum_{j=1}^nA_{ij}^k)\bmod M\)，其中 \(M=998244353\)。

范围：\(1\leq n\leq10^5\)；\(0\leq k\leq M\)；\(a_i,b_i\in\mathbb{R}\)，\(|a_i|,|b_i|\leq10^9\)；

（\(M=998244353\approx10^9\)）

本题中 \(A^0\) 为单位矩阵。

思路

如果用常规矩阵快速幂，求一次矩阵乘法 \(O(n^2)\)，总共 \(O(n\log n^2)\)，显然不行。

考虑推式子。

---

\(A^{2}_{ij}=A_{ij}\times A_{ij}=\sum_{k=1}^n a_ib_k\times a_kb_j=a_ib_j\sum_{k=1}^na_kb_k\)；

不妨记 \(\sigma=\sum_{k=1}^na_kb_k\)，

则 \(A^{2}_{ij}=a_ib_j\sigma\)。

类似地，\(A^{4}_{ij}=A^{2}_{ij}\times A^{2}_{ij}=\sum_{k=1}^na_ib_k\sigma\times a_kb_j\sigma=a_ib_j\sigma^2\sum_{k=1}^na_ib_j=a_ib_j\sigma^3\)。

不难发现，\(A^k_{ij}=a_ib_j\sigma^{k-1}\)。

故：

\[\sum_{i=1}^n\sum_{j=1}^nA_{ij}^k=\sum_{i=1}^n\sum_{j=1}^na_ib_j\sigma^{k-1}=(\sum_{i=1}^na_i)\cdot(\sum_{j=1}^nb_j)\cdot(\sum_{i=1}^na_ib_i)^{k-1}. \]

所以我们只需要用 \(O(n)\) 的时间统计三个 \(\sum\) 的值，然后对 \(\sigma\) 用快速幂，总计 \(O(n+\log n)=O(n)\)，可以通过本题。

编码

• 注意 \(a_i,b_i\) 可能小于零，需要在输入时取一次 \(a_i\gets(a_i\bmod M+M)\bmod M\)。

• 考虑边界情况，\(k=0\) 时 \(\text{ans}=n\)。