AC. 梦想

标签 STUDY 下的文章

多项式运算小结

多项式可以加减乘,这是基本常识。然而,多项式还支持除法、乘方、开方、求对数等等运算,这可实在是有些神奇。于是在此小结一下多项式的诸多运算。在接下来的叙述中,定义多项式A(x) = \sum_{i=0}^{n} {a_i x^i}。 为方便叙述,在下列所有运算中,多项式的运算均定义在\pmod {x……
16/04/01 | 暂无评论 | 3,211阅读 阅读详情

GCD黑科技

来看这样一个问题: 有T组询问,第i组询问给出两个正整数a_i,b_i。对于每组询问,求\gcd(a_i,b_i)。1 \le T \le 10 ^ 7,1 \le a_i,b_i \le 10 ^ 7。 对于一般题目,求一次\gcd(a,b)的时间是\log(n)。但是,在可以预处理的情况下,即a,b是两个在一定范围内的整数时,求\gcd的过……
16/03/25 | 暂无评论 | 3,584阅读 阅读详情

有上下界网络流

有上下界网络流大致可以分为下面几类问题。 在下列叙述中,b(u,v)为边的流量下界,c(u,v)为边的流量上界,f(u,v)为边的实际流量,g(u,v)为边的自由流,即g(u,v) = f(u,v) - b(u,v)。 无源汇有上下界可行流 对于一个在无源汇有上下界网络的可行流,任意边应满足上下界限制b(u,v) ……
16/03/21 | 暂无评论 | 1,559阅读 阅读详情

微积分基本定理

数学真的很重要。这次学习一下微积分基本定理。微积分基本定理描述了微积分的主要运算——微分和积分之间的关系,并给出了定积分的计算方法,极大地简化了定积分的计算。先上定义: 原函数 函数f(x)是定义在某区间的函数。若存在可导函数F(x),满足在该区间上有F'(x) = f(x),则……
16/03/20 | 暂无评论 | 530阅读 阅读详情

矩阵幂求和

考虑这样一个问题 给定n阶矩阵\textbf{A}(n \le 50),求\textbf{S} = \sum_{k=0}^{m} {\textbf{A} ^ k},(0 \le m \le 10 ^ 9)。 矩阵幂求和?我会二分!其实二分也是也是一种不错的方法,不过还有一种方法。我们来分析一下。 二分法 对次数进行二分,递归求出m/2次的答案,利……
16/03/16 | 暂无评论 | 763阅读 阅读详情

矩阵优化递推

以前一直不会独立分析有关矩阵快速幂优化递推的问题,昨天晚上自己给自己出了一道题。想了许久,似乎明白了一点,那么便记录一下吧。 首先贴上自己给自己出的题(引例): 求下列d阶线性常系数递推关系的第n项0 \le n \le 10 ^ {18},将答案\mod 10 ^ 9 + 7输出。f(x) = \sum_{……
16/03/15 | 1 条评论 | 525阅读 阅读详情

割点和桥

这是我基础图论知识的一块漏洞,现在补上~~ 先来看割点的定义: 对于无向图G,如果删除某个点u后,连通分量数目增加,则称点u是图G的割点。 怎样求出一个图所有的割点呢?不难想到一个O(n(n+m))的做法,但这显然不是最优的,考虑其他思路。 我们考虑一个无向图的DFS树,发现无……
16/03/13 | 暂无评论 | 1,291阅读 阅读详情

Linux下对拍脚本

用惯了Windows的bat,转成Linux的sh,还是花了不少功夫的。 先贴上Linux系统下对拍脚本的模板: check.sh Shell #!/bin/bash g++ a.cpp -o a g++ b.cpp -o b g++ dmk.cpp -o dmk # g++ check.cpp -o check i=1 tot=1000 while [ $i ……
16/03/13 | 暂无评论 | 1,290阅读 阅读详情

数论相关线性筛

数论问题中,有许多函数需要我们进行线性预处理。利用欧拉筛法这个强大的算法,我们可以解决某些函数的线性筛。一般情况下,在数论题目中,如果我们要对一个函数线性筛,首先需要证明这个函数是积性函数。 积性函数是什么呢?在数论中,对于某函数f(x),若对任意两个互质的正整……
16/03/09 | 暂无评论 | 745阅读 阅读详情

FFT初遇印象

快速傅里叶变换(Fast Fourier Transform),是一种极为著名的算法,以其巧妙、高效著称。在OI领域的应用主要是多项式乘法(特殊形式是高精度乘法)。多项式乘法似乎还与组合数学有很大的联系,所以对于OI选手,是一种非常有用的必备法宝。 为什么FFT做多项式乘法更快呢?FFT原是……
15/12/12 | 暂无评论 | 1,233阅读 阅读详情