文章

传送门_(:зゝ∠)_ 又觉得别人线段树合并分裂丑要自己写，又写了半天（关键自己写的也挺丑的）首先对于每一个排过序的块，它的值都是有序的，因此每一块连续的排序块我们都用一个权值线段树维护其内含的值 初始的时候就是 $n$个块，每个块一个元素 然后对一段区间排序就是把这个区间内的块都 阅读更多…

题目大意 戳我看题 字符集大小为 $m$，要求你构造一个最短的字符串，使得长度为 $n$的不同子串至少有 $K$个。 题目分析 原来我不会欧拉路.avi 思路很简单，首先，将任意长度为 $n-1$的子串看做节点，每个节点连 $m$条边出去到新的节点。可以证明（但没必要），原图存在一条欧拉回路。于是我 阅读更多…

题目链接 原来传说中的 MTT 就是分系数 FFT 啊。。。 假如我们要求 $(A \times B) \mod MOD$ 做法就是设一个整数系数 $M$ $A\times B = (\lfloor \frac A M \rfloor \times M + A \mod M) \times (\lf 阅读更多…

题目连接 对于 $n$的范围如此巨大得不正常的题目我们通常会考虑用矩阵快速幂解决 能用矩阵快速幂解决的话需要满足状态转移方程是个 “齐次线性常系数递推” 何谓 “齐次线性常系数递推” 呢？ 比如这一题，当 $k$已知，设 $f[i]$表示有 $i$个点时的答案 若存在一个数列 $p$，满足对于 $\ 阅读更多…

题目链接在这 QvQ “ 你要求出这个 n 维球体的球心坐标“，这使我想到的解方程…… 先假设 n=2，这是一个二维平面。设圆心的坐标为 $(x,y)$，有两个坐标 $(a_1,b_1)$和 $(a_2,b_2)$，显然两个坐标的关系为： $(x-a_ 阅读更多…

这是一篇翻译向的文章，笔者整理了一些有关 Berlekamp–Massey 算法的笔记，还增加了一些自己的理解。 下面列出了笔者写此文时所参考的一些资料： wikipedia fjzzq2002 别人的博客 线性递推式 对于一个数列 ${S_i}$，它的 $m$阶递推式 $&#1 阅读更多…

题目链接 被 POJ 大秀了一回 矩阵乘法一开始我是这么写的： #define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) – MOD) #define mul(a, b) ((a) * (b) % MOD) void M_mul(in 阅读更多…

概率论 题意 求 $n$个节点随机二叉树的叶子个数期望。 分析 设所有的 $n$个节点的二叉树的叶子个数之和为 $G$，$n$个节点二叉树的总数为 $C$。 则可以枚举根节点的两个儿子的大小来统计： $$ G[n]=\sum_{i=0}^{n-1}2G[i]C[n-1-i]\\ G[0]=0 阅读更多…

这显然是一道概率的题目 (废话) 设发 $f[i]$表示买到第 $i$张邮票还需要购买的期望次数，$g[i]$表示买到第 $i$张邮票还需要期望花费的钱。 那么答案显然为 $g[0]$，我们来考虑怎么转移。 对于 $f[i]$，有三种情况： 现在有 $\frac{i}{n}$的几率会买到重复的邮票， 阅读更多…

被概率冲昏的头脑~~~ 我们先将样例在图上画下来： 会发现，最大收益是： 看出什么了吗？ 这不就是凸包吗？ 跑一遍凸包就好了呀，这些点中，如果 i 号点是凸包上的点，那么它的 ans 就是自己 (第二个点)，不然的话，从上图来看，i 的 ans 肯定和他相邻的两个是凸包边界的点有关 (0 节点和 2 阅读更多…