标签 STUDY 下的文章
多项式运算小结
多项式可以加减乘,这是基本常识。然而,多项式还支持除法、乘方、开方、求对数等等运算,这可实在是有些神奇。于是在此小结一下多项式的诸多运算。在接下来的叙述中,定义多项式A(x) = \sum_{i=0}^{n} {a_i x^i}。
为方便叙述,在下列所有运算中,多项式的运算均定义在\pmod {x……
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的过……
有上下界网络流
有上下界网络流大致可以分为下面几类问题。
在下列叙述中,b(u,v)为边的流量下界,c(u,v)为边的流量上界,f(u,v)为边的实际流量,g(u,v)为边的自由流,即g(u,v) = f(u,v) - b(u,v)。
无源汇有上下界可行流
对于一个在无源汇有上下界网络的可行流,任意边应满足上下界限制b(u,v) ……
微积分基本定理
数学真的很重要。这次学习一下微积分基本定理。微积分基本定理描述了微积分的主要运算——微分和积分之间的关系,并给出了定积分的计算方法,极大地简化了定积分的计算。先上定义:
原函数
函数f(x)是定义在某区间的函数。若存在可导函数F(x),满足在该区间上有F'(x) = f(x),则……
矩阵幂求和
考虑这样一个问题
给定n阶矩阵\textbf{A}(n \le 50),求\textbf{S} = \sum_{k=0}^{m} {\textbf{A} ^ k},(0 \le m \le 10 ^ 9)。
矩阵幂求和?我会二分!其实二分也是也是一种不错的方法,不过还有一种方法。我们来分析一下。
二分法
对次数进行二分,递归求出m/2次的答案,利……
矩阵优化递推
以前一直不会独立分析有关矩阵快速幂优化递推的问题,昨天晚上自己给自己出了一道题。想了许久,似乎明白了一点,那么便记录一下吧。
首先贴上自己给自己出的题(引例):
求下列d阶线性常系数递推关系的第n项0 \le n \le 10 ^ {18},将答案\mod 10 ^ 9 + 7输出。f(x) = \sum_{……
割点和桥
这是我基础图论知识的一块漏洞,现在补上~~
先来看割点的定义:
对于无向图G,如果删除某个点u后,连通分量数目增加,则称点u是图G的割点。
怎样求出一个图所有的割点呢?不难想到一个O(n(n+m))的做法,但这显然不是最优的,考虑其他思路。
我们考虑一个无向图的DFS树,发现无……
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 ……
数论相关线性筛
数论问题中,有许多函数需要我们进行线性预处理。利用欧拉筛法这个强大的算法,我们可以解决某些函数的线性筛。一般情况下,在数论题目中,如果我们要对一个函数线性筛,首先需要证明这个函数是积性函数。
积性函数是什么呢?在数论中,对于某函数f(x),若对任意两个互质的正整……
FFT初遇印象
快速傅里叶变换(Fast Fourier Transform),是一种极为著名的算法,以其巧妙、高效著称。在OI领域的应用主要是多项式乘法(特殊形式是高精度乘法)。多项式乘法似乎还与组合数学有很大的联系,所以对于OI选手,是一种非常有用的必备法宝。
为什么FFT做多项式乘法更快呢?FFT原是……
12