欧几里得算法 为什么要放欧几里得算法，因为这个玩意是扩展欧几里得的铺垫，为什么要将扩展欧几里得，因为这个玩意是中国剩余定理的铺垫。很简单，就是要我们求。由于证明过程十分繁琐并且没有什么很大的意义，所以便不多管闲事地证明了，结论也很简单：。于是可以不断递归，直到j变成0，然后返回i就可以了，很常见的方法，直接放代码了。 inline int Gcd(int X, int Y) { if (Y == 0) return X ; return Gcd(Y, X % Y) ; } 裴蜀定理 裴蜀定理是扩展欧几里得算法的第二个铺垫，也是一个关于最大公约数的定理。假设有一个线性方程，问这个...

浅谈关于动态规划问题的优化方案 很多动态规划的题目不仅仅要求正确性，还要求极快的速度，因此有时单纯的动态规划手段也可能超时，于是便需要一些适当的优化，本文主要浅略地谈一下使用单调队列或者斜率知识优化动态规划问题的手段。 1.单调队列优化 单调队列是一种具有单调性的队列，其中的元素全部按照递增或者递减的顺序排列，就比如下面这个递减队列。 假如说我们要在队尾加入一个，那么我们入队的步骤就是这样的： 发现队尾，(q[tail])，，则将1退出(tail--) 发现队尾，(q[tail])，，则将2退出(tail--) 发现队尾，(q[tail])，，则将3退出(tail--) 发现队尾，(q[...

概念 卢卡斯定理要解决的问题很简单： 如果规定为质数，那么就用卢卡斯定理解决，否则就是扩展卢卡斯定理。洛谷上两个模板题都有 Lucas ExLucas 前置知识 如果你不知道前置的知识的话，最好还是去系统学习一下。 1. 乘法逆元 若且与互质，则称的意义下的乘法逆元为 关于求逆元：因为所以所以所以的逆元为直接快速幂就可以了。 2.扩展欧几里得 扩展欧几里得用来在求得的同时，找出整数使其满足 3.费马小定理 。 4.中国剩余定理 还请移步博客欧几里得与扩展中国剩余定理Excrt 卢卡斯定理 证明过程：首先根据组合数的只是我们可以很显然推出 $ 然后根据二项式定理得出： 然后我们继续从...

插值法及拉格朗日插值多项式 插值，适用于解决复杂、难于计算的函数表达式问题的有力手段，更有时根本没有具体的函数，只有对应采样点的几个函数值，而要求计算非采样点的函数值的问题，此时插值法就可以构造出该函数的近似表达式来解决问题。本文主要介绍拉格朗日插值法，具体包括其工作原理，改进法，性质应用和代码实现。 ：“插值”，适用于解决复杂、难于计算的函数表达式问题的有力手段，更有时根本没有具体的函数，只有对应采样点的几个函数值，而要求计算非采样点的函数值的问题，此时插值法就可以构造出该函数的近似表达式来解决问题。 一：什么是插值 插值是属于数学数值分析领域的内容，常被称作内插或者插值。接下来给出定义：...

文章被题目大致分为了两个部分：线性积分和 傅里叶变换。其实这么分实际上是不甚妥当的，因为傅里叶变换就是线性积分变换中的一种。如果要结合题目细讲，写起来怕是一个浩大的工程了，因此讲解的内容大多就仅止步于在信息学奥赛中的应用。当然，博主也会尽力深挖，争取让文章不只是初步。 写在前面 很多人学快速傅里叶变换，学它的微分关系，学它的卷积特性，但是始终都没有思考过这个玩意是干嘛用的。毕竟本篇文章实际上想要讲的就是傅里叶变换，我们也首先要了解到傅里叶变换的作用是什么。 从数学上来说，傅里叶变换是用于解决两个多项式的 卷积，简单来说就是两个多项式相乘的次数，如果直接暴力计算，那么时间复杂度应该是，而快速傅里...

莫比乌斯反演初步和实际应用 定义和一般形式及其证明 假设有数论函数关系式，则有 此为基本定义，但是看到这个函数也有限制就是必须是数论函数。，也就是定义域为正整数，对应集合为复数的函数。下面是函数的一般形式。 假设d定义在上的复值函数，则有 而这个函数就是莫比乌斯函数，其定义如下： 时，。 ，（为互异素数），则 其他情况下 由定义可以得到莫比乌斯函数的两个重要性质： 对任意正整数有 证明 : 设有 代入得 由于的限制条件为，所以等式写成: 证明完毕。 代码实现 用线性筛法求莫比乌斯函数，时间复杂度 inline void Init() { memset(V, 0, s...

CSP-S RP+++++++++++++++++++++++++++

我这边是windows，下了sublimelinter和sublimelinter-cppcheck 但是他并不能有用。 debug 也已经是 true了，不是很懂配置怎么弄。 有大佬用SublimeLinter吗？？

我自己在本校的OIER里面算是非常菜的了。 上一年的NOIP之前备战，队长让自己出题，自己造数据然后给同伴弄成考试。 我就自己出了一道题。 我还依稀记得这道题被排在T3整个团队没有一个人想出来任何解法的时候自己内心的兴奋。 当时放在那个时候算是非常难的了，往后也出不出来这么综合，这么有水平的题了。 原来叫做Samsara，后来在洛谷的比赛里面，被学长拿去用了，改了题面。 放上链接吧。然后这个题的题解里面的叫做Sue_Shallow的就是我的最初题解啦。 依稀想到那时候的凌云壮志，还满能感慨的。  [yLOI2018]锦鲤抄-洛谷 https://www.luogu.org/problem/P5008

并查集。可以发现只有奇数环或者是偶数环才会影响到最终结果，因此出现奇数环我们踢掉一个人，出场人数为奇数也要踢掉一个人。因此我们考虑用并查集维护两个点之间的关系，如果他们位于同一个集合之中并且是一个奇数环，那么答案加一就可以了。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; const int MAXN = 1100 ; const int MAX...