B_M

分类

Codeforces(5) java课(7) 分治(1) 动态规划(1) 图论(1) 数学(11) 数据结构(2) 算法课(13)

/ 注册

全部文章（共41篇）

数学-Convolution

题目传送门题目大意求解题思路这还是camp的题，当时不会，甚至想过莽，因为签完到别的题也不会了原式等于因为，所以那么原式就相当于其中的求和就相当于是卷积，我们构造一个以作为指数，作为底数的项的多项式则答案就是该多项式平方后所以先然后枚举求和其中也就是关于的二次剩余 AC代码 //#...

2020-02-26

0 600

数学-拉格朗日插值

拉格朗日插值公式是次多项式复杂度为一些特殊条件下可以优化一道裸题题目传送门：622F-The Sum of the k-th Powers 题目大意求因为模数的关系，显然不可以这题其实是拉格朗日插值的裸题解题思路令通过低次的规律可以发现，应该是一个次的多项式，我们可以通过拉格朗日插值求...

2020-02-25

0 469

数学快速数论变换

NTT 将FFT中的的值改为,对取模即可,为的原根，其中的值需要有足够大的的幂次因子比如将记作，在意义下与具有相同的性质性质如下 1.为的原根，因此两两不相同2.3.4.所以可以与等价，用来快速变换模板 void NTT(ll y[],int len,int rev) { change(...

2020-02-23

0 511

数学-离散傅里叶变换

离散傅里叶变换是一种快速进行多项式乘法的方法，朴素的多项式乘法时间复杂度一般为,通过离散傅里叶变换，时间复杂度可以优化到多项式的表示方法系数表示法我一直以来学习的多项式表示方法都是系数表示法，简单来说就是其中是阶多项式其中是阶多项式那么对于这两个多项式的乘...

2020-02-22

0 562

数学杜教筛

杜教筛杜教筛用来解决积性函数前缀和的问题，可以在低于线性的时间复杂度内求出前缀和求欧拉函数前缀和记欧拉函数前缀和已知所以先枚举则原式等于上面一步相当于先枚举其中一个因子为,则只要那么就一定是中某个数的因子，而原式的含义就是将中所有数的因子的相加然后我们发现所以右边部分可以预处理大约个，再...

2020-02-20

0 463

1307D Cow and Fields

题目传送门题目大意给出一张图，个点，条边，图上每条边的边权为图上有个特殊点，两两之间可以连边，已经有边的也可以连边连一条边，问图上到的最短路的最大值是多少解题思路从号点和号点各一遍，记正向距离为，反向距离为，则答案为稍微变换一下，原式变为按照升序排序枚举每一个位置，最小值一定是,让这个值最...

2020-02-20

0 575

数学-Dirichlet卷积

在oi-wiki上学了不少，做一点笔记积性函数定义若对于任意的总有则函数称为积性函数若对任意的，都有则函数称为完全积性函数性质若和都是积性函数，则都是积性函数举例单位函数恒等函数——x是几就是几常数函数——x是几都是1欧拉函数——且与互质的数的个数莫比乌斯函数 Dirichlet卷积...

2020-02-17

0 719

数学-CCPCwintercamp-3D. 求和

题目传送门题目大意令,求思路则原式等于用莫比乌斯函数和的卷积替换一下枚举e，e为的因子，和为的倍数 e的倍数显然有个令这一步显然和为的两个因子，且,所以我们可以先枚举,然后枚举,这样因为莫比乌斯函数和函数的卷积是欧拉函数所以最后交换一下和得到枚举T，原式等价于...

2020-02-16

0 455

1285E Delete a Segment

题目传送门题目大意给出个的区间，有交叉的区间可以合并为同一个，从中删去一个，最多可以形成多少个独立的区间思路若是没有删去一个的条件，对于所有的区间可以先对升序排序，然后用栈进行合并1.插入一个新的区间，若栈顶的区间的，将栈顶区间退栈，退栈的区间与待插入的区间可以合并为新的待插入区间2.重复1...

2020-02-14

0 490

数据结构-采蘑菇的克拉莉丝(树链剖分)

题目传送门之前一直没弄明白如何利用轻重链来维护答案，重新思考了一下以后明白了题目大意给出一棵树，树上每个点有点权，每个边有边权2种操作1.增加点权2.改变根Q次询问，每次询问完成当前操作后当前从当前根节点出发摘掉所有蘑菇的花费，每个蘑菇的花费为从根节点出发到蘑菇所在位置路径上距离根节点最近的边...

2020-02-12

0 529