数学相关【真·NOIP】

数论相关

上来就不会的gcd相关。见SCB

~~他威胁我去掉了一个后缀~~

的blog好了：

https://blog.csdn.net/suncongbo/article/details/82935140

（已经过本人同意）

CRT大体式子应该是记住了233。如下。

$P=\prod _{i} p_{i}$

$P_i=\frac{P}{p_i}$

$T_i=P_i^{-1}mod\ p_i$

$X=\prod_i x_iP_iT_i$

方便记忆的话就是我们首先要求所有的pi的lcm然后自己不用算进去就是Pi因为要除掉就是逆元就都乘起来就好了qwq

（这是因为我太弱了所以找了个办法记下来qwq）

这次也是对积性函数和dirichlet卷积有了一个较为准确的认识（你之前是真的蠢

积性函数满足交换律结合律都很好证就不写了

莫反的原因其实就是因为μ和1是逆元所以就可以莫反了qwq

组合计数相关

基本式子啥的不写了（扩展Lucas应该不会考叭不管了QAQ不过好像扩展Lucas并不难…留个坑叭

第一类Stirling

$\begin{bmatrix} n\\m \end{bmatrix} =(n-1)\begin{bmatrix} n-1\\m \end{bmatrix} + \begin{bmatrix} n-1\\m-1 \end{bmatrix}$

n个数排成m个非空环的方案数

貌似这玩意不怎么考（因为好像没有优化

生成函数扔上来吧

$x^{\bar{n}}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i$

$x^{\underline{n}}=\sum (-1)^{(n-i)} \begin{bmatrix}n\\i\end{bmatrix}x^i$

上面的是上升幂式子大概是这个样子

$x^{\bar{n}}=\sum \begin{bmatrix}n\\i\end{bmatrix}x^i=(x^0+\begin{bmatrix}n\\0\end{bmatrix})*(x^1+\begin{bmatrix}n\\1\end{bmatrix})*...$

下降幂就是把+改成-

这个我不会233只不过看到网上找不到上升幂下降幂的定义我就写一下（说不定还写错了QAQ

第二类Stirling

$\begin{Bmatrix} n\\m \end{Bmatrix} =m\begin{Bmatrix} n-1\\m \end{Bmatrix} + \begin{Bmatrix} n-1\\m-1 \end{Bmatrix}$

n个元素分成m个无序非空集合的方案数（区别于插板，n个元素相互区分）

$x^n=\sum_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}$

$m!\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^{m}(-1)^{m-i} \binom{m}{i}i^n$

这几个式子都还不大理解但是先留下以后再看吧

插值

不管不管我就只学拉格朗日插值

$g_i(x)=\prod_{j=0\ j\neq i}^n \frac{x-x_j}{x_i-x_j}$

$f(x)=\sum_{i=0}^{n}y_ig_i(x)$

挺直观的（虽然还没写过

然后剩下的时间都挂机了

主要是minmax容斥，自然数幂和，伯努利数，差分序列…

讲题人精心准备的题目，难度适中，思路清晰，简直就是NOIP难度好题。233。

Update：真的需要总结一下NOIP的数学相关了

数论

1.GCD

辗转相除法 gcd(a,b)=gcd(b,a%b)

证明：令
$c=gcd(a,b), a=mc,b=nc$
。
$gcd(mc,nc)=gcd(nc,(m \ mod \ n)c)$
。证毕。

在用的时候一定记得传参a是较大的数，b是较小的。

相关结论：
$gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1$
，
$gcd(Fib(a),Fib(b))=Fib(gcd(a,b))$
。以上两个证明见scb的blog。

2.EXGCD

求解
$ax+by=gcd(a,b)=d$
或者
$ax \equiv b \ (mod \ m)$
这两个式子是等价的（一定有解，见裴蜀定理）

推导：设我们已经得到了一组解
$(p,q)$

$\\ap+bq=gcd(a,b)=gcd(b,a \% b)=bp+(a\%b)q \\ =bp+(a-(a/b)*b)q=aq+b(p-(a/b)q)$

终止条件当
$b==0$
时，
$gcd(a,b)=a$
，
$ap+bq=a\ (b==0)$
解得
$p=1,q=0$
。

递归回去就好了qwq

贴一份代码吧

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

如果要求非负整数解的话。
$p=p+b,q=q-a$
加减对方系数就好了

裴蜀定理我也写一下吧

对于
$gcd(a,b)=d$
，一定存在
$d\mid ax+by$
。

证明：令
$a=nd,b=md$
。有
$d\mid ndx+mdy$
显然成立。

3.缩系及相关

定义？集合S满足
$0<S_i<m$
，
$gcd(S_i,m)=1$
。

集合中数的个数称为
$\varphi (m)$
。

若
$gcd(a,m)=1$
，则有
$a^{\varphi (m)} \equiv 1 (mod\ m)$
。（欧拉定理）

证明：对于
$S_1,S_2...S_{\varphi(m)}$
它们模m应该是互不相同的，所以
$aS_1,aS_2...aS_{\varphi(m)}$
模m应该也是互不相同的（很显然啊QAQ）

所以这两个集合中的数应该是一一对应的。（见缩系的定义）

把它们乘起来
$\prod_{i=1}^{\varphi(m)} S_i \equiv a^{\varphi(m)} \prod _{i=1}^{\varphi(m)}S_i(mod\ m)$
Si的乘积肯定是和m互质的所以可以除掉。就剩下
$a^{\varphi(m)}\equiv1(mod\ m)$