引入 一个 $n$ 个点有向图的邻接矩阵 $A$ 是一个 $n$ 阶布尔矩阵，它的幂组成的序列具有周期性。 设 $k,d$ 是满足 $A^k=A^{k+d}$ 的最小正整数，则 $k$ 称为 $A$ 的幂敛指数（index），$d$ 称为 $A$ 的周期（period）。 对于如下邻接矩阵 $A$，其各次幂分别为 $$A^1 = \left[\begin{matrix}0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0…
题目描述 [https://www.luogu.org/problemnew/show/P4173] 给你两个带通配符的串 $A,B$。问 $B$ 中可以匹配多少个 $A$，并输出匹配的开头位置。 思路 我们在两个长度相同的字符串 $A, B$ 上定义 $f(A, B)=\sum_{i=0}^{n-1}(A_i – B_i)^2A_iB_i$。令通配符 * 为 0，当 $f(A,B)=0$ 时，$A = B$。 将 $f$ 展开得 $\sum_…
Intro 跑去上海打了这两场考试，结果惨不忍睹 (╯‵□′)╯︵┻━┻ 所以我取消了最近几天的行程专心写题 _(:з)∠)_ 本文缓慢更新，一些神仙题可能我一辈子都改不出来。 由于洛谷的新版界面丑陋不堪，除非迫不得已，将不提供洛谷的原题链接。 Day 1 异或粽子 [https://loj.ac/problem/3048] 简述题意 给定一个数列，求前 $k$ 大的区间异或值的和。 吐槽 > 它不希望用同样的馅儿的集合做出一个以上的粽子。 这句话被我理解成了 “不希望用同样的馅儿 的集合”，以至于我认为所有集合是互斥的。成功爆零。 思路 我们对这个数列做一下前缀异或，令得到的数列为 $s$，问题实际上就是求 $k$ 个数对 $(i,j),1\le i\le j \leq n$，使得 $s[i-1] \ \text{…
定义 Splay 是一种可以自我调节的二叉搜索树。它在 $\Theta(\log n)$ 的均摊时间内执行基本操作，例如插入，查找和删除。对于许多非随机操作序列，Splay 比其他搜索树表现更好。 核心操作 我们提到 Splay 可以 “自我调节”，这一性质使得它能维持树形结构，保证复杂度。自我调节分为两部分：旋转 (rotate)，以及伸展 (splay)。 旋转 伸展 实际运用 作为二叉搜索树，它能完成所有二叉搜索树都能完成的基本操作。当然，它也可以作为区间树完成诸如区间翻转的操作，正是这一性质使得它可以作为 Link Cut Tree 的辅助树。 代码 普通平衡树 [https://www.luogu.org/problemnew/show/P3369] 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：…
Dirichlet Convolution Definition $$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{xy=n}f(x)g(y)$$ Example * $\sigma_0=1*1$ * $\sigma_1=I*1$ * $I=\varphi*1$ * $\epsilon(n)=\mu*1$ Property * 交换律：$f*g=g*f$ * 结合律：$(f*g)h=f(g*…
Intro 咕了一年的集合。NOIp 内容。 （实际上只讲了两个函数） 常见数论函数 * $\epsilon(n)=[n=1]$ * $1(n)=1$ * $id_k(n)=n^k$ * $I(n)=id_1(n)=n$ * $\sigma_k(n)=\sum\limits_{d|n}d^k$ * $\varphi(n)$ * $\mu(n)$ 欧拉函数 $\varphi(n)$ Definition $\varphi(n)$ 等于小于等于 $n$ 且与 $n$ 互质的正整数个数，即 $$\varphi(…
> 还有什么能够盛开 你知道我一直很乖 我们的过去是一片稻田 还有什么值得期待 mama don’t let me down mama go with the wind 蒲公英和炊烟都在等你 你的孩子一直很乖 mama don’t let me down mama go with the wind 蒲公英和炊烟都在等你 你的孩子一直很乖…
题目描述 [https://www.codechef.com/APRIL14/problems/FBCHEF] Chef declared war on Byteland. Chefs best scientist Pramod has designed a new Fighter Plane which can fly with Speed of Light!! So none of the defence forces of Byteland can defeat or defend it. Byteland has a structure of a tree…