当前位置: 首页 > news >正文

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\)

http://www.hskmm.com/?act=detail&tid=25216

相关文章:

  • P9751 [CSP-J 2023] 旅游巴士
  • P9234 [蓝桥杯 2023 省 A] 买瓜
  • P1044 [NOIP 2003 普及组] 栈
  • P1080 [NOIP 2012 提高组] 国王游戏
  • 音响没声音
  • P1654 OSU!
  • DynamoDB十年演进:云原生数据库的技术革新
  • 完整教程:MySQL全量、增量备份与恢复
  • 10/5
  • 10/4
  • 嵌入式MCU
  • porting perf性能观测工具
  • Windows常用快捷指令
  • Python 在金融中的应用- Part 1 - 教程
  • QBXT2025S刷题 Day4
  • java学习日记9.25
  • porting 开源memtester
  • 计算机的组成
  • 完整教程:用mediamtx搭建简易rtmp,rtsp视频服务器
  • oppoR9m MTK 6755 开启VCOM的9008模式
  • 关于电脑息屏后自动亮屏的的原因排查及解决方式
  • 机器人世界杯工业联赛技术解析
  • Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) A~E
  • k8s之基础概念
  • 251005
  • Java基础 Day26 - 详解
  • 14_mklink创建符号链接
  • 7_如何构建知识图谱
  • 点双连通分量例题:矿场搭建
  • MTK oppoR9m Smart Phone flash Tool 提示 ERROR: STATUS_UNSUPPORT_CTRL_CODE (0xC0010004)