问题解决-逻辑 P8110 [Cnoi2021] 矩阵-分析
最编程
2024-06-01 16:06:35
...
以样例1为例：
3 0
1 2 3
4 5 6
根据题意，A_{ij}=a_i\times b_j，很容易得到：
$$
A= \begin{bmatrix} 4&5&6\\ 8&10&12\\ 12&15&18\\ \end{bmatrix}
$$
A= \begin{bmatrix} 4&5&6\\ 8&10&12\\ 12&15&18\\ \end{bmatrix}
$$
诶，有没有发现一个特殊的性质？
矩阵A的行和列线性相关1！！！
从而，矩阵A的秩r(A)=1，于是有一个结论2：
$$
A^k=\tr(A)^{k-1}A
$$
A^k=\tr(A)^{k-1}A
$$
其中，\tr(A)称为矩阵A的迹，即A的主对角线上的元素之和（在这里即\sum_{i=1}^{n}a_ib_i）
那么，此题已解。
$$
\begin{align} Ans&=\tr(A)^{k-1}\sum_{i=1}^{n}\sum_{j=1}^{n}{A_{ij}} \\&=(\sum_{i=1}^{n}a_ib_i)^{k-1}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\cdot b_j} \\&=(\sum_{i=1}^{n}a_ib_i)^{k-1}\sum_{i=1}^{n}{a_i}\sum_{j=1}^{n}{b_j} \\&=(\sum_{i=1}^{n}a_ib_i)^{k-1}(\sum_{i=1}^{n}{a_i})\cdot(\sum_{j=1}^{n}{b_j}) \end{align}
$$
\begin{align} Ans&=\tr(A)^{k-1}\sum_{i=1}^{n}\sum_{j=1}^{n}{A_{ij}} \\&=(\sum_{i=1}^{n}a_ib_i)^{k-1}\sum_{i=1}^{n}\sum_{j=1}^{n}{a_i\cdot b_j} \\&=(\sum_{i=1}^{n}a_ib_i)^{k-1}\sum_{i=1}^{n}{a_i}\sum_{j=1}^{n}{b_j} \\&=(\sum_{i=1}^{n}a_ib_i)^{k-1}(\sum_{i=1}^{n}{a_i})\cdot(\sum_{j=1}^{n}{b_j}) \end{align}
$$
快速幂处理(\sum_{i=1}^{n}a_ib_i)^{k-1}即可
时间复杂度：O(n+\log k)