8.27 T2 炫酷原神（DP+矩阵快速幂+dDP）
8.27 T2 炫酷原神（dp+矩阵快速幂+ddp） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141609749 <cplusoj.com/d/senior/p/SS240827B> 这道题时间够慢慢做还是能做的，至少思路是很顺的，就是系数太难调了 考虑一个朴素的dp， f[i][c][j][t]f[i][c][j][t]f[i][c][j][t] 表示考虑前 iii 个字符，文章末尾有 jjj 个 ccc ，当前剪贴板上是 ttt 的概...
8.26 T2 日记和欧拉函数（欧拉函数）
8.26 T2 日记和欧拉函数（欧拉函数） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141575260 http://cplusoj.com/d/senior/p/NOD2301B 发现 x≤Bx\le Bx≤B 时答案是 xxx x>B+500x>B+500x>B+500 左右答案是1 我们预处理中间的就行 预处理直接暴力做，求 maxϕ\max \phimaxϕ 的话相当于求小于它的质数 12345678910111213141...
8.26T1 日记和最短路（二分 哈希 倍增）
8.26T1 日记和最短路（二分 哈希 倍增） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141575217 http://cplusoj.com/d/senior/p/NOD2301A 题解做法复杂度是错的，hack掉了 比较两个字符串常见方法是二分加hash 在这题套个倍增就行 题解做法也有可取的，把一个串拆成一堆小字符，实现起来方便很多 最后我打了9k 复杂度两只log 123456789101112131415161718192021222324...
8.22 万灵药（SAM + Trie + 树剖 + 线段树）
8.22 万灵药（SAM + Trie + 树剖 + 线段树） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141438811 http://cplusoj.com/d/senior/p/479?tid=66c55d60c098fe0f6786d470 考虑如何求两个前缀的最长后缀 我们建一个SAM，把这两个前缀找出来，他们的公共后缀集合为这两个点在fail树上的公共祖先 那么最长后缀就是它们lca对应的最长串 接下来我们要统计这些串的前缀，首先肯定要拿一...
8.22 T4 （吉司机线段树）伤痕累累的心，在暴雨中仍然放声歌唱
8.22 T4 （吉司机线段树）伤痕累累的心，在暴雨中仍然放声歌唱 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141429914 http://cplusoj.com/d/senior/p/SS240709D 假设现在只有 [1,x][1,x][1,x] 考虑一个数的贡献区间为 r−l−1r-l-1r−l−1 ， l,rl,rl,r 为左右第一个比它大的数的坐标 此时的答案是 ∑r−∑l−x\sum r-\sum l-x∑r−∑l−x 。我们不妨先算 ∑...
8.22 T3 escape from whk 3（2次幂相关）
8.22 T3 escape from whk 3（2次幂相关） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141426364 http://cplusoj.com/d/senior/p/SS240709C 考虑一个 [l,r][l,r][l,r] 区间，我们有什么策略？ 性质1：我们从大到小，能选就选，肯定最优 如果按照这样子，我们可以发现选出来的数肯定长成这个样子 因此我们可以： 这样子对于一个 [l,r][l,r][l,r] 的复杂度是 O...
8.21T1 草莓蛋糕（拆max + 权值线段树）
8.21T1 草莓蛋糕（拆max + 权值线段树） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141403142 http://cplusoj.com/d/senior/p/NODSX2302A 看到式子： 我们就应该想到拆max 若 我们可以整理推出： 记： 由 LLL 算 CCC ，我们满足 ha≤hbh_a\le h_bha≤hb ，找 ccc 的最小值 CCC 算 LLL 同理。 我们直接拿权值线段树实现就行 但是叶子节点有很多信息...
8.21 T2 矩阵补全（FWT）
8.21 T2 矩阵补全（FWT） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141403062 http://cplusoj.com/d/senior/p/NODSX2302B 考虑 bi∈{1}b_i\in\{1\}bi∈{1} 怎么做，这是个裸的FWT，FWT后弄个快速幂就行 如果 bi∈{0,1}b_i\in\{0,1\}bi∈{0,1} ，在0的位我们就要保持原样不能动 若 bi∈{0,1,2,3}b_i\in\{0,1,2,3\}bi∈...
8.20T3 无损加密（线性代数转LGV+状压DP+高维前缀和）
8.20T3 无损加密（线性代数转LGV+状压dp+高维前缀和） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141373559 http://cplusoj.com/d/senior/p/NODSX2301C 对于式子： 这个神秘的线性代数形式比较难处理，但我们可以考虑其组合意义。行列式现存的可用组合意义之一就是LGV（矩阵式不太可用） 先把原先的矩阵转化为一个有向图。现在我们要构造一个图，满足 Bi,jB_{i,j}Bi,j 代表从 aia_iai...
8.20T2 黑色大桥（函数处理、李超线段树）
8.20T2 黑色大桥（函数处理、李超线段树） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141362275 http://cplusoj.com/d/senior/p/NODSX2301B 有一个显然的dp： dpj=maxi≤j(dpi−1+Fi(j−(i−1)))dp_j=\max_{i\le j}(dp_{i-1}+F_i(j-(i-1)))dpj=maxi≤j(dpi−1+Fi(j−(i−1))) 答案是 dpndp_ndpn ，复...
