B_M

数学

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

/ 注册

全部文章 / 数学（共11篇）

数学-卡特兰数

卡特兰数卡特兰数的基本公式通项公式变形公式递推公式基本形式给出个元素，其中个元素，个元素，要求对于由两种元素按顺序排列组成的序列中，任意一个前缀的数量不少于,有多少种组合方式个节点的二叉树共有多少个可以将一棵二叉树分为根，左子树，右子树三部分，枚举左子树节点个数，则共有种不同的二叉树

2020-04-28

0 403

数学-miller_rabin测试

miller_rabin素性测试给出一个非常大的数，判断它是不是素数对于较小的数，可以枚举内每一个数试除，若能整除则非素数，这么做的复杂度为对于较大的整数，如级别的数，不够用了所以去学了一下miller_rabin测试法miller_rabin测试法是一个随机算法，虽然不能保证完全正确，但是判断6...

2020-04-21

0 469

数学 tsy's number

题目传送门题目大意求解题思路欧拉函数有一条性质一个整数可以表示为因为欧拉函数是积性函数，所以上下约分后同理所以原式等于枚举，原式用换个元交换一下枚举顺序最右边求个和，用其中所以最右边记作原式变为令交换一下枚举顺序，原式变为合并一下中间部分是一个迪利克雷卷积的形式，是...

2020-02-27

0 460

数学-Polynomial

题目传送门题目大意给出,个询问，每个询问求解题思路很明显的拉格朗日插值但是一直化简不出来之后看题解发现了一个常识之前也用过，但是死活想不起来，果然还是我太菜有了这个常识这题就变得简单了，先插值求然后做前缀和此时就变成了前缀和所表示的多项式的前项；此时再插值求出来的就是前缀和的值了即可...

2020-02-26

1 598

数学-Convolution

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

2020-02-26

0 515

数学-拉格朗日插值

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

2020-02-25

0 398

数学快速数论变换

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

2020-02-23

0 425

数学-离散傅里叶变换

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

2020-02-22

0 431

数学杜教筛

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

2020-02-20

0 369

数学-Dirichlet卷积

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

2020-02-17

0 599