典型的反转 ，整理一下此类题思路。 题意简述 你现在要按照如下方式生成一个长度为 的数组： 对于 ，有 的概率设 ，有 的概率设 。 对于一个长度为 的数组，计算 。特别地，。此时 数组的最大前缀和 。现在给定 个正整数 。该数组最大前缀和为 时，该数组的分数为 。 要求对于所有 ，求出生成出的数组的期望分数对 取模的结果。 。 思路分析 正向考虑困...

Day 1 8:00 走进考场。啊，是熟悉的首师附机子，像是回家了一样。啊，是熟悉的 sublime，像是回家了一样。 近视越发严重，看不见解压密码。感谢好心的监考打开了教室中间的屏幕。 8:30 开 T1，疑惑是否读错了题。反复确认题面再看样例，才发现题目就是这么搞笑。20min 切了。 8:50 看 T2 T3，发现都很神秘。感觉 T2 实在是更神秘一筹。想到了一些边双之类的，于是开始...

题意简述 有 个人在数轴上等速移动，每个人有一个初始方向，两人相遇时，有 的概率左边的人会消失， 的概率右边的人会消失，求最终恰有 个人抵达数轴最左端， 个人抵达数轴最右端的概率。 复杂度要求 。 题解 首先，我们找到最靠右的抵达数轴左端点的人 ，那么最靠左的抵达数轴右端点的人一定在他的右边，且一定恰是 。简单分类讨论易证。 接下来，我们枚举 所在的位置，分别求其左...

拉格朗日插值 考虑对于一个多项式 。给出 上 个点 ，它们唯一确定一个 次多项式。 考虑构造多项式 ，定义域为 ，使得当且仅当 时，，其余情况下 。假设我们找到了这样的 ， 显然就是 。 考虑这样一个函数： 它便符合上述条件。那么，我们就可以得到： 自然数幂和 求形如 的值。 首先，证明上述 是一个关于 的 次多项式。 我们求一次差分，即...

FFT 功能 快速傅里叶变换， 时间复杂度快速完成点值表达式和系数表达式的转换。一般搭配生成函数等等食用。 由于点值表达式相乘大大快于多项式卷积，所以先将多项式通过 转化为点值表达式，对应点（单位根处的值）相乘后使用 转化回多项式的形式。 基本公式 其中 是一个 次多项式， 和 分别是 取出偶次项和奇次项形成的多项式。具体过程： 所以： 至此推导完毕...

反演 https://vfleaking.blog.uoj.ac/slide/87#/炫酷反演魔术ICPC WC 2014 Day 7 以上是神级学习资料。 反演的本质 本质上来说，反演的时候我们一般会遇到形如下面式子的形式： 其中 是我们希望求得的答案， 容易直接计算得出， 是系数。一般来说，我们可能会看到形如这样的描述：设 表示恰好拥有 个属性的方案数， 为不超...

考场心路历程 14:10 走进考场。这键盘好酷炫啊。随便敲敲键盘。 14:20 开始解压题目。T1 好像会做。 14:30 开码 T1，此时没有注意到四个景点互不相同的条件。 14:50 注意到了条件。想了 ，不会。开 T2。 16:30 调完 T2，切窗口眼测过了大样例。不放心又写了个 check。估分 。 16:45 开 T3。 17:00 有了 T3 暴力思路。 17:50 T3 码...

结论题可爱 题意简述 给出一个字符串 ，你可以使用一个印章，每次能印出一个相同的字符串 ，印章印过的地方可以重叠，但是重叠部分的字符必须相同。求最小的印章长度，。 思路分析及证明 首先可以想到 。设 代表恰好覆盖 的长度为 的前缀 所需要的最小的印章长度。 通过尝试，我们容易发现如下引理。 引理0：若 能够恰好覆盖 ， 能够恰好覆盖 ，则 能恰好覆盖 。 证明：...

爹级思维题。为什么是 T0 啊 nmd 题意简述 给出一个栈，你需要向其中按顺序投入 个弹珠，弹珠有 种不同颜色，你可以投入任意颜色的弹珠。如果栈顶部 颗弹珠颜色是相同的，你需要将它们取出。现在，要求求出能够使所有弹珠都被取出的投入方案数。 数据范围：。 思路分析 分析个头。分析不出来。直接讲做法。 考虑如果采用传统的方法，会发现状态与状态之间的重复极其难以处理。也就是...

KMP 可爱的初级字符串算法。是某钻石教练会讲的算法。复杂度线性。 前缀数组（nxt） 定义： 代表 子串 最长的相等的真前缀与真后缀的长度（字符串下标从 开始）。规定 。 可以这样理解： 的意思是将字符串整体向右挪动，当 到达 的位置时，第一次出现前缀与原位置完全吻合。这样，当 位失配时，我们只需要将 挪到 的位置，保证前 位都是正确的，更改第 位。 可...