wxyww

精品

未归档(12) 题解(65)

/ 注册

全部文章 / 精品（共28篇）

莫比乌斯反演

重新学习了一遍莫比乌斯反演，整理一下。莫比乌斯函数莫比乌斯函数是一个积性函数。$x1.x=1\mu(x)=12.x\mu(x)=(-1)^kkx3.\mu(x)=0$莫比乌斯函数是个积性函数，所以可以线性筛。性质 $2.$ 线性筛莫比乌斯函数代码 for(int i = 2;i &l...

2020-05-29

1 713

【题解】牛客练习赛64

A 怪盗-1412 problem 用个，个，个进行排列，求最多有多少个子序列。 solution 显然让所有的4和2分别相邻答案会更大。然后就是将1分成两份，分别放在4两边。如果前面的有个，那么答案就是，这是一个二次函数，当时取得最大值。 code /* * @Author: wxyww * @D...

字符串贪心动态规划

2020-05-24

2 724

线性代数基础

[toc] 线性方程组概述线性方程组就是形如下方的方程组。初等行变换与高斯消元线性方程组有3种初等行变换（将某行乘以某个数，将两行相减，交换两行）通过三种初等行变换，我们可以进行高斯消元。高斯消元其实就是平时解方程组的过程。大体过程就是通过第i行消去每行(除第i行)的第i个未知数的系数...

2020-05-22

2 683

数hash

树的同构两棵树如果形态相同，就称这两棵树同构。也就是：存在一个排列，将其中一棵树的编号改为，使得这棵树和另外一棵树完全相同。树hash 判断两棵树是否同构可以使用树hash的方法。用表示i这棵子树的hash值。那么有，表示第个素数。表示以为根的子树的大小。dfs一遍即可求出。任意点为根的has...

2020-05-22

1 538

博弈论

SG函数作用对于一个状态i为先手必胜态当且仅当SG(i)!=0。转移那怎么得到SG函数尼。 SG(i)=mex(SG(j))（状态i可以通过一步转移到j）首先说一下mex。一个集合的mex是最小的没有出现在这个集合里的非负整数。其实想一下这个也是挺明显的。状态i是先手必败态当前仅当i转移...

2020-05-22

1 502

用杜教筛求解数论函数前缀和

杜教筛用来求数论函数前缀和。复杂度为前提如果我们要求，那么需要找到一个数论函数，满足的前缀和可以非常快速的求出来，并且的前缀和可以非常快速的求出来。推导既然的前缀和可以非常快速的求出来，我们就求的前缀和。即。然后我们想得到的是。所以我们让上面的式子减去一个。对于后面这个式子,我们用来代...

2020-05-22

1 570

快速沃尔什变换小记

概述是用来处理集合卷积的问题。也就是求解类型的问题。其中或运算可以改为。寻找点值因为总是看不下去那么长的推导，所以每次都是看到一半。然后就在加上自己的一点理解，简单推导一下吧（背过结论就行）以或运算为例。为什么说是集合卷积呢。因为或运算等价于求集合并。也就是求。那么我们类似于，先将他转化...

2020-05-22

1 563

数学知识点整理

这篇文章主要是整理一些定理，方便后面复习。没有证明(学OI要什么证明)。数论相关常见的积性函数单位函数欧拉函数表示小于等于n的数字中与n互质的数字个数。莫比乌斯函数正因子数因子函数易知一般记作常值函数幂函数特别的，常记作狄利克雷卷积对于两个数论函数，其中*为狄利克雷卷积...

数学

2020-05-22

1 631

【题解】牛客练习赛61

迟到1h，险些掉分，呼~ A 数据范围很小，模拟签到题。 /* * @Author: wxyww * @Date: 2020-04-10 19:52:33 * @Last Modified time: 2020-04-10 20:02:50 */ #include<cstdio> #in...

搜索动态规划点分治

2020-04-11

1 609

【题解】牛客OI周赛15-提高组

环球旅行题意就是给出一棵带边权的树。删除上面的一条边，使分成的两棵树中较大的直径尽量小。求该直径。【20分做法】枚举删除哪条边，计算直径。复杂度【30分做法】对于菊花图，删除最长边即可。【40分做法】对于一条链，枚举删边，可以直接算出剩下两条链的直径。【60分做法】对于且数据随机的...

2020-04-04

2 543