多项式完全模板 多项式 +,−+,-+,− 多项式乘法 多项式求逆 多项式开根 多项式求幂 多项式 ln\lnln 多项式 exp\expexp 多项式整除/取模 多项式立方根(upd@11.28),支持任意常数项(平方根同) 常数项二次/三次剩余BSGS求解复杂度 O(p)O(\sqrt{p})O(p) #include <bits/stdc++.h 2021-11-27
Icpc 济南区域赛 Optimal Strategy 有 n 件物品,第 i 件的价值为 a[i]。A 和 B 轮流取物品,A 先手。每个玩家都要最大化自己取到的物品的价值和,求有多少种可能的游戏过程。 1 <= n <= 1 000 000 1 <= a[i] <= n 考虑最大值如果是偶数个,那么会每次被两个两个的取;如果是奇数个,那么会被先手立刻取走一个,变成偶数的情况。 故容易得 2021-11-22
一道极限题 $ limh→0(x+h)h−1h=1\lim\limits_{h \to 0}\frac{(x+h)^h-1}{h} =1h→0limh(x+h)h−1=1 $ 引理 $ limx→0ex−1x=1\lim\limits_{x \to 0}\frac{e^x-1}{x}=1x→0limxex−1=1 $ $ proof. limx→0ex−1x=limx→0xln(x+1)p 2021-10-31 学习
一些题目 记录最近的一些题目 CF 1600E 得到一个性质:只有从头开始的连续上升子串才能被取(因为要求每次取的数是严格递增的),结尾也是一样。 于是只需要考虑前 ppp 个和后 qqq 个数。 当 ppp qqq 都是偶数时,显然后手必胜(每次都取先手取的数的后一个数) 当 ppp qqq 有一个奇数时,显然先手必胜(第一步取奇数侧,变成必败态) 当 ppp qqq 都为奇数时,先手必胜(取第一项大的 2021-10-15 solution #构造 #数学
Code::Blocks 快速上手 Overall codeblocks支持单文件编译运行,但是必须再project内才能使用debug 一个project内的源文件会合并编译,所以一般一个文件一个工程。 环境 编译 先安装minGW 安装codeblocks时可以直接选择。 编译/运行 快捷键 Function Shortcut Key 构建 Ctrl + F9 编译当前文件 Ctrl + Shift + F9 2021-09-29 工具 #工具
树链剖分 #10138. 「一本通 4.5 例 1」树的统计 #include <bits/stdc++.h> #define rep(i, a, b) for (int i = (a); i <= (b); i++) #define per(i, a, b) for (int i = (a); i >= (b); i--) #def 2021-09-29 图论 #模板 #树链剖分
快速数论变换(NTT) 前置知识 问题引入 FFT用的是浮点运算,并且用到了 sin cos\sin \; \cossincos 函数,运算效率比较低并且精度不足。 而NTT用的是数论变换,都是整数运算。 原根 https://oi-wiki.org/math/number-theory/primitive-root/ https://zhuanlan.zhihu.com/p/166043237 NTT 模数 p 2021-09-09 数学 #多项式 #NTT
快速傅里叶变换(FFT)简介 问题引入 求多项式乘法 关于多项式 多项式除了用系数表示法外,还可以使用点值表示法。显然用 n+1n+1n+1 个点就能表示一个 nnn 项多项式。 表示为: $ f(x)={(x0,y0),(x1,y1),⋯ ,(xn,yn)}f(x) = \{(x_0,y_0),(x_1,y_1), \cdots,(x_n,y_{n})\}f(x)={(x0,y0),(x1,y1),⋯,(xn,yn 2021-09-07 数学 #FFT #多项式
树状数组进阶应用 单点修改,区间查询 普通树状数组即可,略。 区间修改,单点查询 树状数组维护差分数组即可。 区间修改,区间查询 还是考虑维护差分数组。 易知: $ ai=∑j=1ibja_i=\sum\limits_{j=1}^i b_jai=j=1∑ibj $ 那么 aaa 的前缀和: si=∑j=1iaj=∑j=1i∑k=1jbk=∑j=1i(i−j+1)bj=(i+1)∑j=1ibj−∑j=1ij×b 2021-08-25 数据结构 #树状数组
一些凸包有关的算法 判断点在凸包内 主要介绍二分法^l1 二分法 如图, 可以通过向量叉积得到任意 V0Vi→\overrightarrow{V_0V_i}V0Vi 和 V0P→\overrightarrow{V_0P}V0P 的左右关系。 先通过 V0V1→\overrightarrow{V_0V_1}V0V1 和 V0Vn−1→\overrightarrow{V_0V_{n-1}}V0Vn−1 2021-08-24 计算几何 #凸包