标签 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
[NOI 2015] 品酒大会
[APIO 2015] Jakarta Skyscrapers
为什么呢？
梦在信息学