The Art of Coding

Here's something encrypted, password is required to continue reading.

md 源代码：https://pastebin.ubuntu.com/p/jrxgSSQXqJ/

-1. Prologue

致考试前挑灯夜战的你们：

恭喜你们，你们胜利了。

我不敢猜宗老师是怎么想的，但既然期末题出成了这样，那我得认。期末八道题，第一第二第六三题跟去年期末一模一样，第三题是第十五周作业原题，第四题的粘合在作业中出现过很多次，第五题简单，第七题更是简单的发指，生怕你想不出例子与证明。唯独只有一道与课上证明内容强相关的第八题，可它却只有区区十分，期末考试却有整整一百分。

Markdown 源代码：https://pastebin.ubuntu.com/p/Jvm2f6jWhW/

分节次的笔记（清华云盘）：https://cloud.tsinghua.edu.cn/d/2c4efaca588a4326958d/

00. Lecture Info

1. 考核

作业 20%、期中 30%、期末 50%

2. 作业

每周四上午 9：50 之前提交

3. 答疑

周二下午 2:00-3:00 荷二 103

4. 内容

• 基础内容：点集拓扑、代数拓扑
• 拓展内容；

包含 Dinic 费用流 无/有源汇网络流

包含 KMP Trie AC自动机 dp/矩阵优化AC自动机

题目简述

给定一串长度为 \(n\) 的序列，每个点上有一个权值 \(a_i\) ，现在你需要处理 \(q\) 个操作，有以下两种操作：

\(1\) \(val\)

表示你需要构造一个序列，序列中每一个元素 \(seq_i\) 小于等于 \(a_i\) 且大于 \(0\)，问所有合法的序列中 \(val\) 出现了几次。

\(2\) \(pos\) \(val\)

表示把 \(pos\) 号节点的点权修改为 \(val\)，点的编号从 \(0\) 开始。

对于每一个询问 \(2\) ，请输出操作的结果 \(mod\) \(p\)，\(p\) 为质数。

引言

当我们对一个矩阵进行快速幂时，我们可能需要对矩阵的某一行进行求和，即计算矩阵 \(A\) \(A^1 + A^2 + A^3 + A^4 + A^5 + \ldots + A^n\) 中的第一行的和。

如何解决？