NOIp复习

在放弃集训,又很久没碰OI的情况下,需要改变一下OI学习方式。我决定试一下这种知识点复习方式,向文化课靠拢……

这里将写一些比赛前必须看的复习内容,包括重要结论和模板之类的,希望整理的过程中能有收获。顺序可能随时变动,并且主要根据个人喜好,敬请谅解。

数学

数学部分在联赛中的难度一般不大,但有了去年结论题的教训,千万勿忘打表。规定

(a,b)=gcd(a,b)(a,b)=\gcd(a,b)

欧拉函数(phi)

φ(n)=i=1n[(i,n)=1]=n×p is prime factor of np1p\varphi(n)=\sum_{i=1}^n [(i,n)=1]=n\times \prod_{\text{p is prime factor of n}}\frac{p-1}p

对于质数pp

φ(p)=p1\varphi(p)=p-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int phi(int n)
{
int ans = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
{
while (n % i == 0)
n /= i;
ans = ans / i * (i - 1);
}
if (n > 1)
ans = ans / n * (n - 1);
return ans;
}

时间复杂度O(n)\mathcal O(\sqrt n)

欧拉定理和费马小定理

pp为质数时,有

快速幂(qpow)

注意范围,以及应用费马小定理来处理幂取模和求逆元。

1
2
3
4
5
6
7
8
9
10
11
int qpow(long long a, int b, int p)
{
long long ans = 1;
do
{
if (b & 1)
ans = ans * a % p;
a = a * a % p;
} while (b /= 2);
return ans;
}

若运算复杂度为O(k)\mathcal O(k),时间复杂度O(klogb)\mathcal O(k\log b)

扩展欧几里得(exgcd)

ax+by=(a,b)ax+by=(a,b)的解。如果右边不等于(a,b)(a,b),那么无整数解。令a=a/(a,b),b=b/(a,b)a'=a/(a,b),b'=b/(a,b),则x,y也是ax+by=1a'x+b'y=1的解,而x=x+kb,y=y+ka,kZx'=x+kb',y'=y+ka',k\in \mathbb Z也是一组解。

!important
1
2
3
4
5
6
7
8
9
10
11
12
13
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
int ret = exgcd(b, a % b, x, y), t = x;
x = y;
y = t - a / b * x;
return ret;
}

时间复杂度O(loga)\mathcal O(\log a)

逆元(inv)

,若(a,b)1(a,b)\neq 1无解。当bb不是质数时,用exgcd解同余方程比求aφ(b)1a^{\varphi(b)-1}快;当bb是质数时,求ab2a^{b-2}更加方便。

线性逆元

在模pp下的逆元inv[]inv[](n<pn<p)。一般有两种方法。

另一种不需要记忆,计算阶乘取模fact[]fact[],求出fact[n]fact[n]的逆元,然后递推得出阶乘逆元inv[]inv[]。显然ii的逆元为fact[i1]inv[i]fact[i-1]*inv[i]

筛法

的质数、每个数的最小质因数、欧拉函数等。一般推荐线性筛,就不写埃氏筛了。

!important
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for (int i = 2; i <= n; i++)
{
if (!minp[i])
{
p[++pn] = i;
minp[i] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= pn && i * p[j] <= n; j++)
{
minp[i * p[j]] = p[j];
if (i % p[j] == 0)
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
else
phi[i * p[j]] = phi[i] * (p[j] - 1);
}
}

组合数(comb)

,超过杨辉三角,下面是一些简单的方法。

如果pp为质数,且n,m<pn,m<p,直接用阶乘逆元预处理即可。复杂度预处理O(n)\mathcal O(n),询问O(1)\mathcal O(1),这也是最常用的方法,例如n=106,p=109+7n=10^6,p=10^9+7

1
2
3
4
5
6
7
8
9
10
int comb(int n, int m)
{
return 1ll * fact[n] * inv[n - m] % MOD * inv[m] % MOD;
}
fact[0] = 1;
for (int i = 1; i <= N; i++)
fact[i] = 1ll * fact[i - 1] * i % MOD;
inv[N] = qpow(fact[N], MOD - 2);
for (int i = N - 1; i >= 0; i--)
inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

如果pp为质数且较小,用Lucas定理 。复杂度预处理O(p)\mathcal O(p),询问O(logn)\mathcal O(\log n),例如n=1018,p=106n=10^{18},p=10^6

!important
1
2
3
4
5
6
7
8
9
10
11
12
int comb(int n, int m, int p)
{
if (m > n)
return 0;
return 1ll * fact[n] * inv[n - m] * inv[m] % p;
}
int lucas(long long n, long long m, int p)
{
if (!n)
return 1;
return 1ll * comb(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}

如果pp为任意数,可以线性筛质因子约分快速幂。复杂度O(n)\mathcal O(n),例如n=106n=10^6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int comb(int n, int m)
{
for (int i = n - m + 1; i <= n; i++)
cnt[i]++;
for (int i = 1; i <= m; i++)
cnt[i]--;
for (int i = n; i > 1; i--)
if (minp[i] < i)
{
cnt[minp[i]] += cnt[i];
cnt[i / minp[i]] += cnt[i];
}
int ans = 1;
for (int i = 1; i <= pn && p[i] <= n; i++)
ans = 1ll * ans * qpow(p[i], cnt[p[i]], mod) % mod;
return ans;
}

如果pp为任意数,且mm很小,可以暴力分解质因数。复杂度O(mn)\mathcal O(m\sqrt n),例如n=109,m=103n=10^9,m=10^3

数据结构

图论

字符串

动态规划