NOIP 数学简结

素数和约数

素数判定

$O(\sqrt n)$：枚举$\leq \sqrt n$的数看是否能整除。
$O(k\log n)$：Miller-Rabin算法，k一般取10，最好取前12个质数LL内稳定判素.

bool Miller_Rabin(int x)
{
    if(x<3||!(x&1)) return x==2;
    int a=x-1,b=0;
    while(!(a&1)) a>>=1,b++;
    int k=10;
    while(k--)
    {
        __int128 y=qp(rd()%(x-2)+2,a,x);
        if(y==1) continue;
        bool can=0;
        for(rint i=1;i<=b;i++)
        {
            if(y==x-1) {can=1;break;}
            y=y*y%x;
        }
        if(!can) return 0;
    }
    return 1;
}

筛法

$O(n\log\log)$：埃氏筛，枚举素数倍数，注意剪枝。

void ishai(int n)
{
	susu[++tot]=2;
	for(rint i=3;i<=x;i+=2)
	if(!use[i])
	{
		susu[++tot]=i;
		for(rint j=i*i;j<=x;j+=2*i) use[j]=1;
	}
}

​ $O(n)$：欧拉筛，利用是否为素数为积性函数来筛，还可以在此过程中记录每个数的一个素因子做到 $O(\log)$ 分解质因数，对于筛积性函数需要定义 $f(p)$ 和 $f(p^k)$ ，并且记录 $low_i$ 表示 $i$ 的最小素因项。

void oshai(int n)
{
	for(rint i=2;i<=n;i++)
	{
		if(!use[i]) susu[++tot]=i;
		for(rint j=1;j<=tot&&i*susu[j]<=n;j++)
		{
			use[i*susu[j]]=1;
			if(!(i%susu[j])) break;
		}
	}
}
void ex_oshai(int n)
{
    f[1]=low[1]=1;
    for(rint i=2;i<=n;i++)
    {
        if(!use[i]) susu[++tot]=i,f[i]=f_p,low[i]=i;
        for(rint j=1;j<=tot&&i*susu[j]<=n;j++)
        {
            use[i*susu[j]]=1;
            if(!(i%susu[j]))
            {
                low[i*susu[j]]=low[i]*susu[j];
                if(low[i]==i) f[i*susu[j]]=f_p_k;
                else f[i*susu[j]]=f[i/low[i]]*f[low[i]*susu[j]];
                break;
            }
            low[i*susu[j]]=susu[j];
            f[i*susu[j]]=f[i]*f[susu[j]];
        }
    }
}

数论分块

利用 $\left \lfloor \frac{n}{i} \right \rfloor$ 只有$\sqrt n$种取值，相同取值的一起计算即可，$r=n/n/l$，k维数论分块是 $O(k\sqrt n)$ 的。

最大公约数

具有可并性，可以用st表/线段树维护。

不断添数的话，总体的 $\gcd$ 只会变化 $\log$ 次。

可以拆位，转化为对各质因数的幂次取min，lcm同理。

同余

裴蜀定理

$ax+by=\gcd(a,b)$必有一组整数解 $(x,y)$，可以拓展到多个的情况。

进一步结论：满足 $ax+by=n(x,y,a,b\in N)$ 有解的 $n$ 任意一对满足 $n_i+n_j\ne a*b-a-b$.

同余方程

扩欧可求 $ax+by=\gcd(a,b)$ 的一组可行解，一解可得任意解，由此可求同余方程 $ax\equiv 1\pmod b$ 解。

void exgcd(int a,int b,int &x,int &y)
{
	if(!b) return x=1,y=0,void();
	exgcd(b,a%b,x,y);
	swap(x,y),y=y-(a/b)*x;
}

扩展欧拉定理

$$\begin{equation} a^b\equiv \begin{cases} a^{b\% \varphi(p)}&\gcd(a,p)=1\\ a^b&\gcd(a,p)\neq 1,b<\varphi(p)\\ a^{b\%\varphi(p)+\varphi(p)}&\gcd(a,p)\neq 1,b\geq\varphi(p) \end{cases} \pmod p \end{equation}$$

费马小定理

对于 $p\in prime\&\gcd(a,p)=1$，有 $a^{p-1}=1$ . 可用于求解逆元。

威尔逊定理

$p$ 为素数 $\Leftrightarrow$ $(p-1)!\equiv -1\pmod p$.

乘法逆元

$O(\log)$ 快速幂，适用于满足费马小定理的情况.

$O(\log)$ 扩欧，即求解同余方程 $ax\equiv1\pmod p$，$\gcd(a,p)\ne 1$ 时无解。

$O(n)-O(1)$ 预处理。

inv[1]=1;
for(rint i=2;i<=n;i++)
	inv[i]=(p-p/i)*inv[p%i]%p;

扩展中国剩余定理

求解模线性同余方程组 $\begin{cases} x \equiv b_1\ ({\rm mod}\ a_1) \\ x\equiv b_2\ ({\rm mod}\ a_2) \\ ... \\ x \equiv b_n\ ({\rm mod}\ a_n)\end{cases}$

考虑如何将两方程合并为一个，考虑将 $x$ 写成两个含待定系数方程的形式，则可列等式，发现是一个不定方程的形式，先用裴蜀定理判无解，再用扩欧求一组特解，回代求出一个特定的 $x$ ，那么新的 $a=lcm(a_1,a_2),b=x\%a$ .

组合数学

二项式定理

$(a+b)^n=\sum \binom n i a^ib^{n-i}$ , $(\sum^t x_i)^n=\sum \binom n {n_1,n_2,...,n_t} \prod^t x_i^{n_i}$

多重排列组合

多重集排列数=多重组合数= $\binom n {n_1,n_2,...,n_t}$ = $\frac n {\prod^t n_i!}$

多重集组合数：若选择数<=最小数量，则问题等价于 $\sum^k x_i=r$ 的非负整数解数目，插板法可得 $ans=\binom {r+k-1} {k-1}$ . 否则考虑容斥原理枚举哪些数选完，$ans=\sum _{p=0}^k(-1)^p\sum_{|A|=p} \binom {k+r-1-p-\sum n_{A_i}} {k-1}$

不相邻组合

$n$ 个相同物品选 $k$ 个不相邻的= $\binom {n-k+1} k$ ，理解为在 $n-k$ 个数里插 $k$ 个不相邻的隔板。

圆排列

$(n-1)!$ ，考虑任何一种普通排列都有n种等价圆排列。

错排

$D_n=(n-1)(D_{n-1}+D_{n-2})=nD_{n-1}+(-1)^n=n!\sum \frac {(-1)^i} {i!}$

组合恒等式

比例公式

$$\binom n k=\frac n k \binom {n-1} {k-1}$$

二项式定理特例

$$\sum (-1)^i\binom n i=[n=0]$$

范德蒙德卷积

$$\sum \binom n i \binom m {m-i}=\binom {m+n} m$$

范德蒙德卷积特例(n=m)

$$\sum \binom n i ^2=\binom {2n} n$$

组合数带权和

$$\sum i\binom n i=n2^{n-1}$$

对消公式

$$\binom n m\binom m k=\binom n k\binom {n-k} {m-k}$$

自卷公式

$$\sum \binom {n-i} i=Fib_{n+1}$$

吸收公式

$$\binom n k k=\binom {n-1} {k-1} n$$

$$\binom n k (n-k)=\binom {n-1} k n$$

平行求和

$$\sum^k \binom {n+i} i=\binom {n+k+1} k$$

上指标求和

$$\sum^n \binom i k=\binom {n+1} {k+1}$$

下指标差求和

$$\sum ^k \binom n i (-1)^i=(-1)^k\binom {n-1} k$$

Lucas定理

$$\binom n m\equiv \binom {n/p} {m/p} \times \binom {n\%p} {m\%p} \pmod p$$

卡特兰数

$$H_n=\sum H_{i-1}H_{n-i}=\frac {H_{n-1}(4n-2)} {n+1}=\frac {\binom {2n} n} {n+1}=\binom {2n} n -\binom {2n} {n-1}$$

​ 含义：① $n$ 个 $1$ 和 $n$ 个 $-1$ 排列使得无负前缀的方案数、② $n\times n$ 网格从左下到右上且不穿对角线的非降路径数、③ 圆上 $2n$ 个点划 $n$ 条线段不交的方案数、④ $n+2$ 个点的凸多边形三角剖分方案数、⑤ 长为 $n$ 的出栈序列数量、⑥ $n$ 个点的二叉树形态数。

斯特林数

1. 第二类斯特林数：

   ${n \brace k}$ 即 $S(n,k)$ ，表示将 $n$ 个数分为 $k$ 个非空集合的方案数.

   $${n \brace k}={n-1 \brace k-1}+k{n-1 \brace k}=\sum^m \frac {(-1)^{m-i}i^n} {i!(m-i)!}$$

2. 第一类斯特林数：

   ${n \brack k}$ ，表示将 $n$ 个数分为 $k$ 个圆排列的方案数。

   $${n \brack k}={n-1 \brack k-1}+(n-1){n-1 \brack k}$$

十二重计数法

1. 球不同盒不同：$m^n$、
2. 球不同盒不同无空：$\sum^m (-1)^i\binom m i (m-i)^n$ （容斥）
3. 球不同盒同：$\sum^m {n \brace i}$
4. 球不同盒同无空：${n \brace m}$
5. 球同盒不同：$\binom {n+m-1} {m-1}$
6. 球同盒不同非空：$\binom {n-1} {m-1}$
7. 球同盒同：DP，$F_{n,m}=F_{n-m,m}+F_{n,m-1}$，考虑全部+1或添0即可
8. 球同盒同非空：$F_{n-m,m}$

线性代数

矩阵乘法

1. 具有结合律没有交换律，可以做快速幂，可以循环展开优化常数。
2. 加速递推、作为表达修改的tag
3. 定长路径统计：定长路径数量即做k次邻接矩阵的矩乘，定长最短路即做k次邻接矩阵的floyd，若统计的是 $\leq$ 加上自环即可。

高斯消元

逐步消成对角矩阵即可，当前元要找所在列中系数绝对值最大的一行，然后对其他行消除该元即可。

1. 解n元一次方程组，答案即为第n+1列。
2. 计算行列式：交换两行时答案取反，最终答案即为对角上的数乘积。
3. 求逆矩阵：在原矩阵右边拼上一个单位矩阵，把左边消成单位矩阵右边就是逆矩阵了，消不出来则无解。
4. 异或方程组：解法同理。

线性基

1. 一般指异或线性基，维护数集的异或集合(不含0，如要统计则考虑e[0]后记录是否出现0，没有被选进线性基的数可等价看作为0)，可以贪心构造，维护点对的异或集合是01trie。

   void insert(int x)
   {
   	for(rint i=50;~i;i--)
   	if(x>>i&1)
   	{
   		if(!e[i]) {e[i]=x;break;}
   		x^=e[i];
   	}
   }
   

   异或线性基的大小只有 $\log V$，合并只能逐个插入是 $O(\log ^2)$ 的，区间线性基可以用前缀线性基来贪心维护，额外维护时间信息，相异或时swap留下时间更大的一项即可。

2. 实数线性基：考虑异或线性基的01改成了实数，性质是相同的，复杂度会高一维。