immix's blog

拉格朗日插值法 过 n+1n+1n+1 个横坐标互异的点 (x1,y1),(x2,y2),⋯ ,(xn+1,yn+1)(x_1,y_1),(x_2,y_2),\cdots,(x_{n+1},y_{n+1})(x1​,y1​),(x2​,y2​),⋯,(xn+1​,yn+1​) 的 nnn 次多项式恰为 f(x)=∑i=1n+1yi∏j≠ix−xixj−xif(x) = \sum_{i=1}^{n+1} y_i \prod_{j\neq i} \dfrac{x-x_i}{x_j-x_i} f(x)=i=1∑n+1​yi​j=i∏​xj​−xi​x−xi​​ 证明 将 n+1n+1n+1 个点代入显然得到结论。 模板 [洛谷P4781] 【模板】拉格朗日插值 给出 nnn 个点，插值出多项式，并求出一个点值，朴素实现是 O(n2)O(n^2)O(n2) 的。 如果要在取模下实现，记得先把分母都乘起来，然后统一求逆元，这样复杂度依然是 O(n2)O(n^2)O(n2)的。 参考代码： 12345678910111213141516171819202122232425262728293031 ...

shell 脚本介绍 略。看下面的代码自行意会 一键测试所有样例 123456789101112131415name=problemg++ $name.cpp -o $name -std=c++14 -Wallfor i in {1..10}do cp $name$i.in $name.in time ./$name diff $name.out $name$i.out -Z > /dev/null if (($?)) then echo 样例 $i 不通过 else echo 样例 $i 通过 fidone 注意这里的 -Z 开关可以自行调整。 $? 指的是上一个命令的返回值。 对拍 12345678910111213141516g++ gen.cpp -o geng++ std.cpp -o stdg++ my.cpp -o mywhile truedo ./gen ./std ./my diff out ans -Z if (($?)) then ...

点分治 淀粉质 常见题目套路：求出具有某一条件的路径个数/求出一条最优的路径 核心思路是：每次选取一个点 uuu ，统计所有经过这个点的路径，然后把这个点删去，对于剩下的森林执行同样的操作。 如何统计？所有经过点 uuu 的路径分成 3 部分，v1−u−v2v_1 - u - v_2v1​−u−v2​，其中 v1,v2v_1,v_2v1​,v2​ 不在同一个子树之中，然后每个点存储需要的信息，最后合并。 统计完点 uuu 后，把它从整颗树里面删去，以后不需要用到它了。 如果每次选取的点都是子树的重心，那么复杂度就能够达到 O(nlog⁡n)O(n \log n)O(nlogn)。 总结一下，就是如下流程： 对于一颗树 TTT： 找到重心作为根。 对每个子树，依次进行如下 3 步操作： i) dfs 求出每个子树的到当前根的信息； ii) 对于子树的所有节点，与前面的子树的信息进行合并求解答案； iii) 将这个子树节点的所有信息合并。 删去根。 对于根的每一个子树，回到第 111 步，直到只剩下一个节点。 信息究竟是什么意思呢？ 举个例子，求树的直径。（这是上文说的求出一条最优的 ...

本文中，若无特殊说明，mmm 代表正整数，ppp 代表质数。 事实上，在题目中我们大多数情况下都是讨论对质数取模的情况。 阶 定义 若 (a,m)=1(a,m)=1(a,m)=1，满足 an=1(modm)a^n = 1 \pmod man=1(modm) 的最小的 nnn 称为 aaa 模 mmm 的阶，记作 δma\delta_m aδm​a。 如果 (a,m)=1(a,m)=1(a,m)=1 不互质，那么不难发现，不存在 nnn，使得 an=1(modm)a^n = 1 \pmod man=1(modm)，故我们不定义 aaa 模 mmm 的阶。 性质 本节中 a,ba,ba,b 均与 mmm 互质。 a,a2,…,aδmaa,a^2,\ldots,a^{\delta_m a}a,a2,…,aδm​a 模 mmm 两两不同。 【引理 1】完全剩余系中与 mmm 互质的剩余类所构成的系称为缩系，缩系内四则运算均封闭。 （证明略） 性质 1 证明： 用反证法，假设存在 1≤i<j≤δma1\le i < j \le \delta_m a1≤i<j≤δm​a，使 ...

数学 = 恐怖 莫比乌斯函数 μ\muμ 为莫比乌斯函数，定义为 μ(n)={1n=10n 含有平方因子(−1)kk 为 n 的本质不同质因子个数\mu(n)= \begin{cases} 1&n=1\\ 0&n\text{ 含有平方因子}\\ (-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\\ \end{cases} μ(n)=⎩⎨⎧​10(−1)k​n=1n 含有平方因子k 为 n 的本质不同质因子个数​ —— 引自 OI wiki 筛法求莫比乌斯函数 考虑 nnn 最小质因数为 ppp，n/p=n′n/p=n'n/p=n′。 若 n′ mod p=0n' \bmod p = 0n′modp=0, μ(n)=0\mu(n)=0μ(n)=0。（含有平方因子） 否则，μ(n)=−μ(n′)\mu(n)=-\mu(n')μ(n)=−μ(n′)。（分类讨论几种情况就能发现） 参考代码： 123456789101112int mu[N],pri[N],cnt;bool not_prime[N];mu[1]=1 ...

区间涂色问题 给定一个序列，操作为将一段连续的区间变为相同的颜色，求最少的操作次数。 题1：涂色 P4170 [CQOI2007] 涂色 - 洛谷 假设你有一条长度为 555 的木板，初始时没有涂过任何颜色。你希望把它的 555 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 555 的字符串表示这个目标：RGBGR\texttt{RGBGR}RGBGR。 每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 RRRRR\texttt{RRRRR}RRRRR，第二次涂成 RGGGR\texttt{RGGGR}RGGGR，第三次涂成 RGBGR\texttt{RGBGR}RGBGR，达到目标。 用尽量少的涂色次数达到目标。 长度 n≤50n\le 50n≤50。 考虑区间 dp。设 dpi,jdp_{i,j}dpi,j​ 表示区间 [i,j][i,j][i,j] 的最少涂色次数。 怎么转移？ 先考虑如下引理： 存在一种最优操作，每次操作的区间为 [l1,r1],[l2,r2],…,[lm,rm][l_1,r_1],[l_2,r_2],\ld ...

我，上紫；爱来自中国🥰 A. Buttons 题意 有 a+b+ca+b+ca+b+c 个按钮，其中 aaa 个按钮只能小 A 按，bbb 个按钮只能小 B 按，ccc 个按钮小 A 小 B 都能按。 小 A 先手，当一个人没有按钮可按时，他就输了。 请问双方都按照最优策略行动情况下，谁会获胜？ 解法 最优策略显然是先按 ccc 然后再按自己的。 所以若 ccc 是奇数，我们给 bbb 减 111。 然后问题就转化成只有按钮 aaa 和 bbb，小 A 先手。显然当 a>ba>ba>b 时小 A 获胜，否则小 B 获胜。 123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define all(x) x.begin(),x.en ...

引言 在信息竞赛中会有这样一类问题，其最终的目标是维护一些变量之间的关系（比如说相等与不等，变量之间的差），对于这类问题的不同变种，我们有不同的方法进行解决。 阅读本文前，我们假设读者已经掌握了如下内容：并查集模板、深度优先搜索、负环判定方法。 维护相等与不相等关系 变量取值任意 模板 给定 nnn 个变量 x1,x2,…,xnx_1,x_2,\ldots,x_nx1​,x2​,…,xn​，mmm 组关系。每组关系形如 xi=xjx_i=x_jxi​=xj​ 或 xi≠xjx_i\ne x_jxi​=xj​。请求出是否存在一组合法解。 解法 对于这个问题，一般解法是利用并查集：我们进行离线处理，先将所有形如 xi=xjx_i=x_jxi​=xj​ 的关系的 (i,j)(i,j)(i,j) 合并到一个集合中，然后再对于所有 xi≠xjx_i\ne x_jxi​=xj​ 的进行检查，如果对应的 (i,j)(i,j)(i,j) 已经被划分到了一个集合中，说明不存在合法解，否则就存在合法解。 时间复杂度 O(n+m)O(n+m)O(n+m)。 习题 [NOI2015] 程序自动分析 同模板 ...

A. United We Stand 题意 给定一个 nnn 的数的序列 aaa，把他分成两个序列 bbb 和 ccc，使得对于所有 cic_ici​ 都不是任意 cjc_jcj​ 的因数。 解法 若 aaa 所有数相同 显然不论怎么分都不可以。 其他 把 aaa 中所有的最大值分到 ccc，其他的分到 bbb，这是一个合法解。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define all(x) x.begin(),x.end()#define mem0(x) memset(x,0,sizeof(x))#define YES puts("YES&qu ...

A - 3.14 题意 π≈3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679\pi\approx 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 π≈3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 输出 π\piπ 精确到小数点第 nnn 位的结果。 解法 用字符串处理即可。 1234567891011121314151617181920212223242526272829#include<bits/stdc++.h>using namespace std;using ll=long long;using ul ...