Sue_Shallow

算法竞赛

题解(1)

/ 注册

全部文章 / 算法竞赛（共6篇）

欧几里得与扩展中国剩余定理ExCrt

欧几里得算法为什么要放欧几里得算法，因为这个玩意是扩展欧几里得的铺垫，为什么要将扩展欧几里得，因为这个玩意是中国剩余定理的铺垫。很简单，就是要我们求。由于证明过程十分繁琐并且没有什么很大的意义，所以便不多管闲事地证明了，结论也很简单：。于是可以不断递归，直到j变成0，然后返回i就可以了，很常见的方...

中国剩余定理扩展中国剩余定理欧几里得

2019-10-31

2 796

浅谈关于动态规划问题的优化方案

浅谈关于动态规划问题的优化方案很多动态规划的题目不仅仅要求正确性，还要求极快的速度，因此有时单纯的动态规划手段也可能超时，于是便需要一些适当的优化，本文主要浅略地谈一下使用单调队列或者斜率知识优化动态规划问题的手段。 1.单调队列优化单调队列是一种具有单调性的队列，其中的元素全部按照递增或者递...

动态规划动态规划的优化

2019-10-31

3 948

卢卡斯定理与扩展卢卡斯定理

概念卢卡斯定理要解决的问题很简单：如果规定为质数，那么就用卢卡斯定理解决，否则就是扩展卢卡斯定理。洛谷上两个模板题都有 Lucas ExLucas 前置知识如果你不知道前置的知识的话，最好还是去系统学习一下。 1. 乘法逆元若且与互质，则称的意义下的乘法逆元为关于求逆元：因为所以所以所...

扩展卢卡斯定理卢卡斯定理

2019-10-31

1 922

插值法及拉格朗日插值多项式

插值法及拉格朗日插值多项式插值，适用于解决复杂、难于计算的函数表达式问题的有力手段，更有时根本没有具体的函数，只有对应采样点的几个函数值，而要求计算非采样点的函数值的问题，此时插值法就可以构造出该函数的近似表达式来解决问题。本文主要介绍拉格朗日插值法，具体包括其工作原理，改进法，性质应用和代码实...

拉格朗日插值

2019-10-31

1 6495

线性积分与傅里叶变换

文章被题目大致分为了两个部分：线性积分和傅里叶变换。其实这么分实际上是不甚妥当的，因为傅里叶变换就是线性积分变换中的一种。如果要结合题目细讲，写起来怕是一个浩大的工程了，因此讲解的内容大多就仅止步于在信息学奥赛中的应用。当然，博主也会尽力深挖，争取让文章不只是初步。写在前面很多人学快速傅里叶变...

线性积分快速傅里叶变换傅里叶变换

2019-10-31

1 1326

莫比乌斯反演初步和实际应用

莫比乌斯反演初步和实际应用定义和一般形式及其证明假设有数论函数关系式，则有此为基本定义，但是看到这个函数也有限制就是必须是数论函数。，也就是定义域为正整数，对应集合为复数的函数。下面是函数的一般形式。假设d定义在上的复值函数，则有而这个函数就是莫比乌斯函数，其定义如下：时，。 ...

莫比乌斯莫比乌斯反演

2019-10-31

1 917