B_M
B_M
全部文章
数学
Codeforces(5)
java课(7)
分治(1)
动态规划(1)
图论(1)
数据结构(2)
算法课(13)
归档
标签
去牛客网
登录
/
注册
B_M_的博客
一只蒟蒟蒟蒟蒟蒻
全部文章
/ 数学
(共11篇)
数学-卡特兰数
卡特兰数 卡特兰数的基本公式 通项公式变形公式递推公式 基本形式 给出个元素,其中个元素,个元素,要求对于由两种元素按顺序排列组成的序列中,任意一个前缀的数量不少于,有多少种组合方式 个节点的二叉树共有多少个 可以将一棵二叉树分为根,左子树,右子树三部分,枚举左子树节点个数,则共有种不同的二叉树
2020-04-28
0
518
数学-miller_rabin测试
miller_rabin素性测试 给出一个非常大的数,判断它是不是素数对于较小的数,可以枚举内每一个数试除,若能整除则非素数,这么做的复杂度为对于较大的整数,如级别的数,不够用了所以去学了一下miller_rabin测试法miller_rabin测试法是一个随机算法,虽然不能保证完全正确,但是判断6...
2020-04-21
0
598
数学 tsy's number
题目传送门 题目大意 求 解题思路 欧拉函数有一条性质 一个整数可以表示为因为欧拉函数是积性函数,所以 上下约分后同理所以原式等于 枚举,原式 用换个元 交换一下枚举顺序 最右边求个和,用其中所以最右边记作 原式变为 令 交换一下枚举顺序,原式变为 合并一下 中间部分是一个迪利克雷卷积的形式,是...
2020-02-27
0
516
数学-Polynomial
题目传送门 题目大意 给出,个询问,每个询问求 解题思路 很明显的拉格朗日插值但是一直化简不出来之后看题解发现了一个常识 之前也用过,但是死活想不起来,果然还是我太菜有了这个常识这题就变得简单了,先插值求然后做前缀和 此时就变成了前缀和所表示的多项式的前项; 此时再插值求出来的就是前缀和的值了 即可...
2020-02-26
1
691
数学-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
数学-Dirichlet卷积
在oi-wiki上学了不少,做一点笔记 积性函数 定义 若对于任意的总有则函数称为积性函数若对任意的,都有则函数称为完全积性函数 性质 若和都是积性函数,则 都是积性函数 举例 单位函数恒等函数——x是几就是几常数函数——x是几都是1欧拉函数——且与互质的数的个数莫比乌斯函数 Dirichlet卷积...
2020-02-17
0
719
首页
上一页
1
2
下一页
末页