OI题目模型记录

· · 个人记录

可能更好的阅读体验

不定时更新（遇到一道好题就会更新）

转换法

有一些题的操作难以实现，这时可以考虑转换法。

  1. P7735 [NOI2021] 轻重边

本题的修改操作较难，故让它第i次修改只是把两点路径上的点染成i颜色。

可以发现，若一条边两点颜色相同，则该边为重边，否则为轻边。

那么询问就变成路径上有几个不同颜色段，用树链剖分+线段树即可，O(n\log^2n)。

  1. CF1334G Substring Search
s_i$与$t_j$匹配需要$s_i=t_j$或$s_i=p(t_j)

转化为(s_i-t_j)(s_i-p(t_j))=0,即s_i^2-s_it_j-s_ip(t_j)+t_jp(t_j)=0

整个字符串匹配成功可以转化为\sum\limits_{i=1}^{|S|}(s_i^2-s_it_{j+i-1}-s_ip(t_{j+i-1})+t_{j+i-1}p(t_{j+i-1}))^2=0

\sum\limits_{i=1}^{|S|}(s_i^2-s_i(t_{j+i-1}+p(t_{j+i-1}))+t_{j+i-1}p(t_{j+i-1}))^2\\=\sum\limits_{i=1}^{|S|}s_i^4-2(t_{j+i-1}+p(t_{j+i-1}))s_i^3+((t_{j+i-1}+p(t_{j+i-1}))^2+2(t_{j+i-1}p(t_{j+i-1}))s_i^2-2(t_{j+i-1}+p(t_{j+i-1}))t_{j+i-1}p(t_{j+i-1})s_i+(t_{j+i-1}p(t_{j+i-1}))^2

将s翻转后即可转化为卷积形式，用NTT可以达到O(n\log n)

  1. P3204 [HNOI2010]公交线路

可以转换为：

  1. 在长度为n的序列里填数，可以填[1,k]内的数
  2. 前k个满足第i个填的是i
  3. 最后k个为[1,k]的排列
  4. 每个长度为p的区间内要包含[1,k]中的所有数
$f_{i,S}+=f_{i-1,S'} (\lfloor\dfrac{S'}2\rfloor\subseteq S,S'\&1=1,\operatorname{popcount}(S)=\operatorname{popcount}(S')=k)

为了保证每个都填，S'\&1必须为1，即第i-1位一定要填

为了保证满足限制4，我们强制转移时[i-1,i+P-2]和[i,i+P-1]都满足[1,k]各填了一个，所以\operatorname{popcount}(S)=\operatorname{popcount}(S')=k

转移的含义：让S中新填的数和第i-1位填的数一样。

初始状态为f_{1,2^k-1}，答案状态为f_{n-k+1,2^k-1}

可以发现状态数为C_{p-1}^{k-1}\leq C_{9}^5=126，可以使用矩阵快速幂优化，时间复杂度O((C_{p-1}^{k-1})^3\log n)

  1. 某题

非空正整数数列\{a_m\}满足\forall k,a_k\geq2，h(n)表示满足\prod\limits_{k=1}^ma_m=n的序列个数，求\sum\limits_{k=2}^nk\times h(k),2\leq n\leq 3.5\times10^7

$k\times h(k)$就是乘积为$k$的序列的乘积之和，所以答案就是乘积在$[2,n]$范围内的序列的乘积之和。 设$f_{i}$表示乘积在$[2,i]$的序列的乘积之和，则有转移方程： $f_{i}=1+\sum\limits_{d=2}^id\times f_{\lfloor\frac{i}{d}\rfloor}$（算上空序列） 答案为$f_n-1

因为\lfloor\frac{\lfloor\frac{n}{a}\rfloor}{b}\rfloor=\lfloor\dfrac{n}{ab}\rfloor，所以所有要算的状态都可以表示为\lfloor\dfrac{n}{x}\rfloor的形式

用整除分块优化可以达到时间复杂度O(n^{0.75})，空间复杂度O(\sqrt n)

  1. [ARC110E] Shorten ABC

将 ABC 分别替换为 123，可以发现一次操作后整个序列的异或和是不变的。

然后由原串 S 得到的新串 T 有个性质：T 的每个字符都对应 S 串的一段区间。

一个区间可以操作成一个字符，要满足下列两个条件之一：

  1. 长度为一
  2. 异或和不为零且包含的字符不全部相同

为了防止算重，每次只选长度最短的区间计算即可。

设 f_{i} 表示 [1,i] 能得到的序列总数，g_{i,j} 表示 i 为左端点，对应字符为 j 的最短区间的长度。

g_{i,j}=\begin{cases}1\qquad\qquad\qquad j=a_i\\g_{i+1,j\oplus a_i}+1\quad j\neq a_i\end{cases} f_{i}\rightarrow f_{i+g_{i+1,j}}

建图优化

当图的边数过多时，用各种方法减少边的数量。

  1. P6378 [PA2010] Riddle

明显的2-SAT问题，但是每个大小为w的部分要建w^2条边，于是用前缀和建图。

原本第i个点有：是/非关键点两种（记为a_{i,1}和a_{i,0}），都要维护一个前缀（记为s_{i,1}和s_{i,0}），再按2-SAT建边。

之后就能把边的个数降为线性。

  1. P6822 [PA2012]Tax

较大值条件难以处理，考虑重新建图。

可以把点看做边，边看做点。但是边又变成n^2级别。

之后把原图中的同一点的出边（单向）按边权排序，并且前缀和建图。

排序后第i条原单向边为u_i权值为w_i，其反边为v_i

则u_i\rightarrow u_{i+1}，边权为w_{i+1}-w_{i}

u_i\rightarrow u_{i+1}$，边权为$0 v_i\rightarrow u_i$，边权为$w_i

这样就实现了较大值并且少了边，之后新开源点和汇点处理起始就可以跑最短路了。

  1. P3783 [SDOI2017]天才黑客

题意：

一条有向路径的长度为这条路径上每个边的边权之和+按照路径的顺序将这些边上的字符串排成一列，相邻两个串的lcp长度之和。求有向图中1号点到其他点的最短路。

和P6822 [PA2012]Tax 很像的一道题，由于lcp长度长度难以处理，所以把点看做边，边看做点。

例如e_i:a\xrightarrow{w_i,s_i} b,e_j:b\xrightarrow{w_j,s_j} c

就连成：a_i\xrightarrow{w_i}b_i\xrightarrow {lcp(s_i,s_j)}a_j\xrightarrow {w_j}b_j

可以发现中间的边是O(m^2)的，考虑前缀和优化。

在字典树上有：(用F[l,r]表示\min\limits_{k=dfn[l]}^{dfn[r]}dep[k])

lcp(s_i,s_j)=dep[lca(s_i,s_j)]=F[s_i,s_j]

假设要连出边的点的集合为b_{1,2,\cdots,k_1}，要连入点的集合为a_{1,2,\cdots,k_2}（都按字典树的dfn排序了）

那么我们只要b_i\xrightarrow{0}b_{i+1},c_{i}\xrightarrow{0}c_{i+1}，b_i\xrightarrow{lcp(b_i,c_{h_i})}c_{h_i},b_{g_i}\xrightarrow{lcp(g_i,c_{i})}c_{i}就能实现让b_i\xrightarrow{lcp(b_i,c_j)}c_j(j\geq h_i)了。

其中h_i指最小的j使得dfn[c_j]\geq dfn[b_i],g_i指最大的j使得dfn[b_j]\leq dfn[c_i]

原理是这样的：F[b_i,c_j](j\geq h_i)=\min\{\min\limits_{k=i}^{b_{g_h}}F[b_k,c_{h_k}],\min\limits_{k=h_i}^{j}F[b_{g_k},c_k]\}（这些区间都包含在[b_i,c_j]内）

这样只向dfn更大的连了边，所以要把e_i拆成四个点a_{i,0/1},b_{i,0/1}并连四条边:a_{i,j}\xrightarrow{w_i,s_i} b_{i,k} (j,k\in\{0,1\})，之后对于b_{i,0}连a_{i,0}的连dfn更大的，对于b_{i,1}连a_{i,1}的连dfn更小的就行了。

新图点的个数和边的个数都是差不多4n，时间复杂度为O(n\log n)。

  1. P5471 [NOI2019] 弹跳
但是本题的点非常少，所以我们考虑用线段树套平衡树(set)来减少空间。 众所周知，dijkstra算法有一个优秀的性质：每个点只会被标记一次，并且权值非负。 在有多个矩形覆盖一个点的时候，我们肯定是用dis最小的矩形来覆盖。 所以我们可以把每个弹跳装置也看做一个点，跑dijkstra的时候就可以保证每个点都是被最优的矩形所覆盖，所以覆盖过一次的节点可以删去。 时间复杂度$O(n\log^2n+(n+m)\log(n+m))$，空间复杂度$O(n\log n)$。 5. [P7712 [Ynoi2077] hlcpq](https://www.luogu.com.cn/problem/P7712) 将水平线段的 $l,r$ 都加上 $n$，加边限制变成：$x,y$ 有连边当且仅当 $l_x\leq y\leq r_x,l_y\leq x\leq r_y$。 考虑 tarjan 算法的过程，递归到 $u$ 时，枚举边 $(u,v)$，若 $v$ 没遍历过则需要递归，否则更新 $low[u]\leftarrow dfn[v]

递归的部分可以 O(n) 枚举，更新则是需要求最小值。

所以用主席树维护未访问过的点个数、访问过的点的 dfn 最小值。

修改点为已访问，只需要改对应的叶节点。在找未访问点时，要么找到有效点，要么更新个数为 0，是均摊 O(n\log n) 的。

矩阵乘法

将一些操作转化成矩阵乘法后，可以利用结合律将其优化至O(\log n)的计算复杂度

  1. P1939 【模板】矩阵加速（数列）
\begin{bmatrix} f_i\\f_{i-1}\\f_{i-2}\end{bmatrix}=\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}\begin{bmatrix} f_{i-1}\\f_{i-2}\\f_{i-3}\end{bmatrix}
  1. P3263 [JLOI2015]有意义的字符串
柿子可以化为$x^n=bx^{n-1}+\dfrac{d-b^2}{4}x^{n-2}$，而且$\dfrac{d-b^2}{4}$还是整数。 设$f_i=(\dfrac{b-\sqrt{d}}{2})^i+(\dfrac{b+\sqrt{d}}{2})^i$，则有$f_i=bf_{i-1}+\dfrac{d-b^2}{4}f_{i-2} \begin{bmatrix} f_i\\f_{i-1}\end{bmatrix}=\begin{bmatrix}b&\frac{d-b^2}{4}\\1&0\end{bmatrix}\begin{bmatrix} f_{i-1}\\f_{i-2}\end{bmatrix}

当n为偶时，0<(\dfrac{b-\sqrt{d}}{2})^n<1

当n为奇时，-1<(\dfrac{b-\sqrt{d}}{2})^n<0

最后输出时判断奇偶即可

  1. P3193 [HNOI2008]GT考试
构造矩阵$A$（只有$A_{0,0}=1$），矩阵$B$，对于每个满足上述条件的$(j,k)$，让$B_{i,j}=1$，其余为$0

之后计算A\times B^n就行。

差不多的一题：见转换法T3:P3204 [HNOI2010]公交线路

  1. P6772 [NOI2020] 美食家
f[t+w][u][v]=\max \{f[t][u][p]+G[p][v]\}(p\xrightarrow{w,G[p][v]} v)

由于w\leq5，把边可以拆成5条长度为1的边，之后变成

f[t+1][u][v]=\max \{f[t][u][p]+G[p][v]\}(p\rightarrow v)

定义广义矩阵乘法C=A*B（可以证明有结合律）：

C_{i,j}=\max\limits_{k}\{A_{i,k}+B_{k,j}\}

令原图邻接矩阵为G，则f[t]=f[0]* G^t

用A来维护ans[1]

然后只要把美食节按时间排序，之后就对于每个1\leq i\leq k：

A\leftarrow A* G^{t_i-t_{i-1}},A[x_i]\leftarrow A[x_i]+y_i

就可以维护每个美食节。

预处理G的2^z次幂（z为整数），由于点的个数为5n，时间复杂度为O(k(5n)^2\log T+(5n)^3\log T)

  1. P6569 [NOI Online #3 提高组] 魔法值

发现a_i很大，n,q很小，就可以发现矩阵乘法的时间复杂度应该是对的。

定义矩阵异或（我自己这么叫）为：

(A\oplus B)_{i,j}=\operatorname{xor}_k A_{i,k}\times B_{k,j}

看看有没有结合律吧：

A\oplus B\oplus C =\operatorname{xor}_{k} (A\oplus B)_{i,k}\times C_{k,j} =\operatorname{xor}_{k} (\operatorname{xor}_d A_{i,d}\times B_{d,k})\times C_{k,j}

乍眼一看就知道没有结合律，但是本题中B,C为01矩阵，还可以进行进一步化简：

上述柿子中A_{i,d}一共异或了\sum_{k} B_{d,k}\times C_{k,j}次，所以上述式子可以化为

\operatorname{xor}_d A_{i,d}\times ((\sum_{k} B_{d,k}\times C_{k,j})\&1) =\operatorname{xor}_d A_{i,d}\times (\operatorname{xor}_{k} B_{d,k}\times C_{k,j})

也就是说，当B,C为01矩阵时是有结合律的。

预处理邻接矩阵的2^z次幂（z为整数），计算答案时只计算第一列。

此时答案为第一行第一列的数，时间复杂度O((n+q)n^2\log a_i)

  1. P3328 [SDOI2015]音质检测

加一矩阵：\begin{bmatrix} F_i\\F_{i-1}\\1\end{bmatrix}=\begin{bmatrix}1&a&b\\1&0&0\\1&0&0\end{bmatrix}\begin{bmatrix} F_{i-1}\\F_{i-2}\\1\end{bmatrix}

减一矩阵：a\not=0时，\begin{bmatrix} F_{i-1}\\F_{i-2}\\1\end{bmatrix}=\begin{bmatrix}0&1&0\\\frac{1}{a}&-\frac{1}{a}&-\frac{b}{a}\\0&0&1\end{bmatrix}\begin{bmatrix} F_i\\F_{i-1}\\1\end{bmatrix}

a=0$时，$\begin{bmatrix} F_{i-1}\\F_{i-2}\\1\end{bmatrix}=\begin{bmatrix}0&1&0\\0&1&-b\\0&0&1\end{bmatrix}\begin{bmatrix} F_i\\F_{i-1}\\1\end{bmatrix}

设V(i)=\begin{bmatrix} F_i\\F_{i-1}\\1\end{bmatrix}，那么第i项的值就是V(A_{i-1}+1)V(A_{i-1}+1)[0][0]

由于是矩阵[0][0]位置的值，我们算(V(A_{i-1}+1)V(A_{i-1}+1)^T)[0][0]也不影响答案，而且有：

用线段树维护区间矩阵和，支持在前或后乘一个新矩阵即可，时间复杂度$O(n\log n)
  1. P7739 [NOI2021] 密码箱

看到它求值的部分是算多次a+\dfrac{1}{b}，于是考虑把它换成矩阵运算使得它能O(\log n)修改。

用\begin{bmatrix} b\\a\end{bmatrix}表示\dfrac{a}{b}，那么计算a+\dfrac{1}{\frac{b}{c}}就可以变成

\begin{bmatrix} b\\ab+c\end{bmatrix}=\begin{bmatrix} 0&1\\1&a\\\end{bmatrix}\begin{bmatrix} c\\b\end{bmatrix}

答案就可以表示成\begin{bmatrix} 0&1\\1&a_0\\\end{bmatrix}\begin{bmatrix} 0&1\\1&a_1\\\end{bmatrix}\cdots\begin{bmatrix} 0&1\\1&a_k\\\end{bmatrix}

然后发现W操作就是使\begin{bmatrix} 0&1\\1&a_k\\\end{bmatrix}变成\begin{bmatrix} 0&1\\1&a_k+1\\\end{bmatrix}

可以变成多乘一个\begin{bmatrix} 1&1\\0&1\\\end{bmatrix}

然后可以发现E操作就是多乘一个\begin{bmatrix} 0&-1\\1&2\\\end{bmatrix}

用平衡树维护修改达到O(n\log n)即可