FFT 与 NTT 算法笔记

设两个多项式分别有 、 个系数: 将乘积展开并按次数合并,得到 这就是线性卷积。直接枚举每一对系数需要 时间。 若改为记录多项式在若干点上的取值,则在每个点 上都有 乘积点值可以通过逐项相乘得到。用点值计算多项式乘法,需要快速完成系数表示与点值表示之间的转换。MIT 6.046J FFT 讲义 次数小于 的多项式由 个

Josephus Problem II

有 个孩子按编号 围成一圈。游戏不断进行:每次跳过 个仍在圈中的孩子,然后删除下一个孩子。要求输出所有孩子被删除的顺序。 约束为 , 。由于 可能很大,不能逐个模拟跳过过程;由于删除次数为 ,也不能在普通数组中直接删除元素,否则总复杂度会达到 。 当前剩余孩子按编号升序排列,可视为一个动态序列。若上一轮删除的是当前序列

Problem: Sliding Window Maximum (LeetCode 239)

给定整数数组 与正整数 ,输出每个长度为 的滑动窗口中的最大值。 - 输入: , - 输出: - 约束: 若窗口内存在下标 且 ,则只要 仍在窗口中, 就不可能成为最大值。因此可用单调递减双端队列维护可能成为最大值的元素下标:遇到更大元素时从尾部弹出较小元素,窗口左边界滑动时从头部弹出过期下标。队列值严格递减,队首即为

算法竞赛 Classic Tricks 复习笔记

- 区间/长度要拆成若干段,每段长度只能取 2 或 3。 - 构造题中需要证明所有 都可写成 ,其中 。 - 原题出现“2 和 3 的倍数组合”时,先把它化成非负整数解问题。 对任意整数 ,都存在 使 若 为偶数,取 ;若 为奇数,则 ,先取一个 3,剩下 为偶数。 - 边权值域很小(如 , ),但边数很多( 很大)。

虚树

给定一棵以 为根的树,并有多次独立询问;第 次询问给出关键点集合 。 - CF613D:可删除非关键点,使任意两个关键点不连通;求最少删除点数。若存在两关键点在原树上相邻,则无解。 - P2495:边有正权。可删除若干边,使根 不可达任何关键点;求最小删除边权和。 两题中,单次询问的 很小,但 与询问总规模很大。若每次

贡献法应用

贡献法适用于答案由大量方案、区间或组合共同构成的情形。直接枚举这些整体对象通常会产生重复计算;更有效的方式是选择一个更小的基本对象,统计它在多少个整体答案中出现,并把“出现次数 单次贡献”累加。 本文的两道题都属于这一类:数组差异题把贡献对象选为排序后的数对或单个元素;函数题把贡献对象选为差分数组中的某个位置。 给定