数学相关【真·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

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

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

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

生成函数扔上来吧

$x^{ar{n}}=sum_{i=0}^{n}egin{bmatrix}n\iend{bmatrix}x^i$

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

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

$x^{ar{n}}=sum egin{bmatrix}n\iend{bmatrix}x^i=(x^0+egin{bmatrix}n\0end{bmatrix})*(x^1+egin{bmatrix}n\1end{bmatrix})*...$

下降幂就是把+改成-

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

第二类Stirling

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

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

$x^n=sum_{i=0}^n egin{Bmatrix}n\iend{Bmatrix}x^{underline{i}}$

$m!egin{Bmatrix}n\mend{Bmatrix}=sum_{i=0}^{m}(-1)^{m-i} inom{m}{i}i^n$

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

插值

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

$g_i(x)=prod_{j=0 j eq 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$ ，一定存在 $dmid ax+by$ 。

证明：令 $a=nd,b=md$ 。有 $dmid 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)$

4.CRT

式子我在一开头写了，直接搬下来了

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

$P_i=frac{P}{p_i}$

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

$X=prod x_iP_iT_i (\%P)$

证明懒得写了QAQ

5.线性求逆元

我们要求x的逆元就要把p表示成x的形式

设 $p=kx+b (k=p/x)$

$kx+bequiv 0(mod p)$

等式两边同乘 $x^{-1}b^{-1}$

$kb^{-1}+x^{-1}equiv 0(mod p)$

$x^{-1}equiv -kb^{-1}(mod p)$

$inv[i]=-p/i * inv[p\%i] (mod p)$

log求单个逆元线性求所有逆元

组合

1.Lucas

$C(m,n)=C(m\%p,n\%p)*C(m/p,n/p)(mod p)$

一些式子

$sum_{i=0}^n C(i,n)=2^n$

$sum_{i=0}^n C(x,i)=C(x+1,n)$ 这个就是杨辉三角上的一列，然后画画图就知道了qwq

$sum_{i=0}^nC(i,k+i)=C(k+n+1,n)$ 还是杨辉三角，只不过是斜着一列，也是可以推出来的

$sum_{i=0}^mC(i,m)C(m-i,n-m)=C(m,n)$ 组合意义

11.1Update

自然数幂和

首先这玩意可以伯努利数or拉格朗日插值（无奈我这俩都不会）所以我们有一个非常暴力的硬推式子方法。

一次二次都比较常见直接贴下来了。

$sum_{i=1}^n i =frac{1}{2}n(n+1)$

$sum_{i=1}^n i^2 =frac {1}{6} n (n+1)(2n+1)$

我来给大家讲一讲怎么硬推三次（雾）感谢scb~~逼我去掉的后缀~~教会的我w

$sum _{i=1}^{n} i^3 = sum _{i=0}^{n-1} (n-i)(3i^2+3i+1)$

我相信你第一步就看蒙了（雾）

其实是这个样子的w

我们对i^3进行差分（相当于对原式进行二次差分）然后我们发现差分后的形式非常吼看（降了一次幂）就可以做啦。

其实就是 $(i+1)^3 -i^3=3i^2 +3i +1$ 。

$sum_{i=1}^n i^3=sum _{i=0}^{n-1} 3ni^2 +3ni +n -3i^3 -3i^2-i$

$4sum _{i=0}^{n-1} i^3 =3n sum_{i=0}^{n-1} i^2+ (3n-1) sum_{i=0}^{n-1} i +n^2 - n^3$

$4sum _{i=-0}^{n-1} i^3 =frac{1}{2} (n-1)(n-1)n(2n-1) +frac{1}{2}(3n-1)(n-1)n -n^2(n-1)$

$4 sum _{i=0}^{n-1} i^3 = frac{1}{2}(n-1)n(2n^2 -3n +1 +3n -1 -2n)$

$sum_{i=0}^{n-1} =frac{1}{4}(n-1)^2 n^2$

$sum _{i=1}^n i^3=frac{1}{4}n^2(n+1)^2$

推这么一波还是很刺激的233

再往上其实都是同理的w

其它

这些可能并不NOIPqwq

线性基（？）传送门

矩乘（？）传送门

斜率优化（？）传送门

高斯消元（？）直接消嘛...

FFT（？）FWT（？）懒得写了QAQ

（为了骗访问量竭尽全力QAQ）