NOIp复习

发表于 更新于 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

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

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

数学

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

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

欧拉函数(phi)

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

对于质数$p$有

$$\varphi§=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;
}

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

欧拉定理和费马小定理

$$a^{\varphi(b)}\equiv 1 \mod b,(a,b)=1$$

当$p$为质数时，有

$$a^{\varphi§}=a^{p-1} \equiv 1 \mod p,(a,p)=1$$

快速幂(qpow)

求$a^b \mod p$。

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

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;
}

若运算复杂度为$\mathcal O(k)$，时间复杂度$\mathcal O(k\log b)$。

扩展欧几里得(exgcd)

求$ax+by=(a,b)$的解。如果右边不等于$(a,b)$，那么无整数解。令$a’=a/(a,b),b’=b/(a,b)$，则x,y也是$a’x+b’y=1$的解，而$x’=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;
}

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

逆元(inv)

求$ax \equiv 1 \mod b$，若$(a,b)\neq 1$无解。当$b$不是质数时，用exgcd解同余方程比求$a^{\varphi(b)-1}$快；当$b$是质数时，求$a^{b-2}$更加方便。

线性逆元

求$1\dots n$在模$p$下的逆元$inv[]$($n<p$)。一般有两种方法。

$$inv[1]=1,inv[i]=(p-p/i)\times inv[p\mod i]$$

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

筛法

求$1\dots n$的质数、每个数的最小质因数、欧拉函数等。一般推荐线性筛，就不写埃氏筛了。

!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)

求$C_n^m\mod p,m\le n$，超过杨辉三角，下面是一些简单的方法。

如果$p$为质数，且$n,m<p$，直接用阶乘逆元预处理即可。复杂度预处理$\mathcal O(n)$，询问$\mathcal O(1)$，这也是最常用的方法，例如$n=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;

如果$p$为质数且较小，用Lucas定理$C_n^m \equiv C_{n\mod p}^{m\mod p} \times C_{n/p}^{m/p} \mod p$。复杂度预处理$\mathcal O§$，询问$\mathcal O(\log n)$，例如$n=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;
}

如果$p$为任意数，可以线性筛质因子约分快速幂。复杂度$\mathcal O(n)$，例如$n=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;
}

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

数据结构

图论

字符串

动态规划