Taduro的一些数学知识

听说学数学对身体好。

为了强身健体，我开始学习数学。这里会更一些数学知识。

其他的东西要不要也写一个知识点汇总呢？

2019/7/7 update:更新辣！！！加入了数数的内容！！！

数论

一些前置知识

数论分块

我知道把这个放在第一个显得很low

如果我们要求一个式子:$\sum_{i=1}^{n} ⌊\frac{n}{i}⌋$ 还是很常见的对吧，由于向下取整$⌊\frac{n}{i}⌋$最多只有$\sqrt{n}$种取值，我们可以枚举取值，算出这个值的个数乘起来

for (ll l=1,r; l<=n; l=r+1){
    if (l<=k) r=min(k/(k/l),n); else r=n;
    ans-=(r-l+1)*(k/l)*(l+r)/2;
}

BSGS及其扩展

求$y^{x}=z(mod\ p)$，给你y,z,p求最小的正整数x。

普通BSGS

保证$gcd(y,p)=1$，用分块思想优化暴力

设$x=a\times m-b$ 那么 $y^{a\times m}=z\times y^b(mod\ p)$

可以枚举b，把$z\times y^b$用哈希存起来，之后枚举a，查表看看有没有对应的b，因为y和p互质，所以并没有什么问题。可以看出$m=\sqrt{p}$时复杂度是最优的。

inline void BSGS(){
    if (y%p==0){puts("Orz, I cannot find x!"); return;}
    y%=p; z%=p; if (z==1){puts("0"); return;}
    ll m=sqrt(p)+1,sq=z; cnt=0;
    memset(head,0,sizeof(head));
    for (int i=0; i<m; i++){
        add(sq%mod,i,sq);
        sq=sq*y%p;
    }
    sq=ksm(y,m);ll sum=sq;
    for (int i=1; i<=m; i++){
        ll u=query(sum);
        if (u!=-1){
            printf("%lld\n",i*m-u);
            return;
        }
        sum=sum*sq%p;
    }
    puts("Orz, I cannot find x!");
}

困难情况

如果$gcd(y,p)=d$呢？

把方程变成$y^x+kp=z$，高次同余方程和一般的一样，要求$gcd(y,p)|z$。可以不断出掉d，最终使y和p互质。

最后式子长这样：$\frac{y^k}{d}y^{x-k}=\frac{z}{d}(mod\ \frac{p}{d})$(除了k个d)，这样我们BSGS解出来的是x-k，加上k就好了。

数论函数基本知识

运算法则

加法：$(f+g)(x)=f(x)+g(x)$，每一项都加起来

乘一个常数：$(k\times f)(x)=x\times f(x)$，每一项都乘x

狄利克雷卷积：两个函数的乘法$f\times g=\sum_{d|n}f(n/d)\times g(d)$(n是两个函数的定义域，需要相同)

卷积满足：

交换律：$f\times g=g\times f$

结合律： $a\times (b\times c)=(a\times b)\times c$

分配率：$a\times(b+c)=a\times b+a\times c$

单位元：$e(x)=[x==1]$，只有在x=1的时候值为1。任何函数和e的卷积都是它本身。

逆元：定义每一个$f(1)≠0$的函数f，都有$f*g=e$，g是f在卷积意义下的逆元。

函数求逆的方法：
$$
g(n)=\frac{1}{f(1)}([n==1]−\sum_{i|n,i≠1}f(i)g(\frac{n}{i}))
$$
这样$f\times g=$$([n==1]-\sum_{i|n,i≠1}f(i)g(\frac{n}{i}))+\sum_{i|n,i≠1}f(i)g(\frac{n}{i})$

对卷积的介绍参考了这篇文章

积性函数

这是很重要的东西。

定义：

积性函数：对于任意互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。

完全积性函数：对于任意整数a和b有性质f(ab)=f(a)f(b)的数论函数。

常见的积性函数

$μ(n)$：莫比乌斯函数
$φ(n)$：欧拉函数
$d(n)$：一个数n的约数个数
$σ(n)$：一个数n的约数和

$1(n)=1$：恒等函数

$id(n)=n$：单位函数

$e(n)=[n==1]$：元函数

两个积性函数的卷积也是积性函数。

众所周知，积性函数有一个重要的性质：$f(i\times j)=f(i)\times f(j)(gcd(i,j)=1)$

求积性函数可以线性筛（杜教筛和Min_25先咕掉）

能筛出的积性函数f必须能快速算出：

1.$f(1)$

2.$f(p)$(p是质数)

3.$f(p^k)$(p是质数)

求出这三个之后我们可以用线性筛求积性函数。

设要求的是f(x)，$x=p1^{a1}*p2^{a2}…$
x只会被它的最小质因子筛到，比如p1
当p1和i互质时，直接$f(p1\times i)=f(p1)\times f(i)$
当p1是i的因子时，根据线性筛得出p1是i的最小质因子
那么我们要记一个low(x)表示x的最小质因子的次幂值，就是$p1^{a1}$
这样$f(p1\times i)=f(low(i)\times p1)\times f(i/low(i))$，显然$low(i)\times p1$跟$i/low(i)$互质对吧。
欧拉筛积性函数的板子：

void sieve(){
    zhi[1]=low[1]=1;
    f[1]=对1直接定义;
    for (ll i=2;i<=n;i++){
        if (!zhi[i]) low[i]=pri[++tot]=i,f[i]=对质数直接定义;
        for (ll j=1;j<=tot&&i*pri[j]<=n;j++){
            zhi[i*pri[j]]=1;
            if (i%pri[j]==0){
                low[i*pri[j]]=low[i]*pri[j];
                if (low[i]==i) f[i*pri[j]]=对质数的若干次幂进行定义(一般由f[i]递推);
                else f[i*pri[j]]=f[i/low[i]]*f[low[i]*pri[j]];
                break;
            }
            low[i*pri[j]]=pri[j];
            f[i*pri[j]]=f[i]*f[pri[j]];
        }
    }
}

实际上很多常用积性函数都不需要这个模板，所以我粘的租酥雨大佬的板子。

莫比乌斯反演

谢特写反演总结要写到死好吧！！！

于是写一些套路好了

1.遇到什么[x==1]直接把他变成$\sum_{d|x}μ(d)$，因为这是元函数，也就是μ跟1的卷积。

$\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)==1]=$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j}μ(d)$

2.遇到[(i,j)==k]直接把i和j的上界除k，相当于枚举k的倍数，就变成$[(i,j)=1]$。

3.遇到两个变量都是自己推出来的可以选择枚举他们的乘积（我猜没人看得懂）

4.为什么我不会用反演公式啊。。。

杜教筛

主要是反演不想写学习笔记

诶你看我不是鸽子吧。。。

杜教筛是用来单次$O(n^\frac{2}{3})$求积性函数前缀和的一种神仙做法，之所以一开始就把时间复杂度说出来是因为我不会证。

以$\mu$为例：求$\sum_{i=1}^n\mu(i)$，不让你$o(n)$做

设$s(n)=\sum_{i=1}^n\mu(i)$

我们要找一个积性函数$g(x)$，把他跟$\mu$卷一下记为h(x)。
$$
h(n)=\sum_{d|n}g(d)\mu(n/d)
$$
求一下这个卷积的前缀和
$$
\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}g(d)\mu(i/d)\
=\sum_{d=1}^ng(d)\sum_{i=1}^{n/d}\mu(i)\
=\sum_{d=1}^ng(d)s(n/d)
$$
g是个积性函数，所以g(1)=1

那么重点来了
$$
g(1)s(n)=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)s(n/d)
$$
完了，如果我们能很快的求h(i)的前缀和和g(d)，就可以递归求出s(n)。

对于$\mu$来说，因为$μ*1=e$，所以g取1。

其实一般杜教筛的时候n都比较大，所以要求o(1)求g(d)，g一般是常函数$e,1,id$什么的，或者是他们的次幂，除去特殊情况不超过3次幂。

奇技淫巧：如果特殊情况g可以取一个也能杜教筛的函数，据神犇wzx说复杂度不变？？？

一些小知识（会更新）：

$μ*id=φ$，也就是： $\sum_{d|n}μ(d)\times\frac{n}{d}=φ(n)$

$φ*1=id$，也就是：$\sum_{d|n}φ(d)=n$ （就是用这个筛$\phi$，g取1，可以自己试试）

多项式与计数

容斥和二项式反演

容斥原理

容斥是你开始做一道数数题的基础，很多数数题都是从容斥开始的。

在很多非数数题中也会出现容斥，也就是用总的情况减去不合法的情况。

当一道题目中出现”至少”或”恰好”这两个字的时候，就要考虑容斥了。

$f_k$表示恰好有k个xxx的情况，$g_k$表示至多有k个xxx的情况，一般$g_k$比较好算。

那么由容斥:
$$
f_k=\sum_{i=0}^k(-1)^{i}C^i_kg_i
$$
组合意义显而易见：至多k种-至多k-1种+至多k+2……那个组合数是因为一个至多包含k个xxx的集合中恰好选出i个xxx有$C^i_k$种情况。

上面一部分是为了下面的二项式反演而写的，其实我常用的容斥是这样：

$f_i$表示恰好，$g_i$表示至少：

$$
f_k=\sum_{i=k}^n(-1)^{i-k}C^i_kg_k
$$

其组合意义显然。

二项式反演

这跟容斥是一个东西。。。

接着上面的容斥，如果我们知道了$f_k$要求$g_k$($g_k$表示至多)，那么就是：
$$
g_k=\sum_{i=0}^k(-1)^iC^{i}_{k}f_i
$$

$$
f_k=\sum_{i=0}^k(-1)^{i}C^i_kg_i
$$

嗯就是一模一样，由于用得少，我不知道这个东西的组合意义，所以证明就是把它带进去，懒得写了。

但我常用的二项式反演是这样的：
$$
g_k=\sum_{i=0}^kC^i_kf_i
$$

$$
f_k=\sum_{i=0}^k(-1)^{k-i}C^i_kg_i
$$

这个组合意义很明显，懒得写了。

应用（从神仙yyblog里抄的）：染色问题：

有$1×n$的一排格子，有$m$种颜色，每个格子染一个颜色，相邻格子颜色不能相同，每种颜色都至少被用到1次，求染色方案数。

先考虑至多k种颜色$g_k$，那么第一个格子有k种填法，其他n-1个格子有k-1种填法，所以：
$$
g_k=k\times (k-1)^{n-1}=\sum_{i=0}^kC^i_kf_i
$$
要求的是$f_m$，用上面的式子带进去：
$$
f_m=\sum_{i=0}^m(-1)^{m-i}C^{i}_{m}g_i
$$

$$
=\sum_{i=0}^m(-1)^{m-i}C^i_m\times i\times (i-1)^{n-1}
$$

组合计数

emmm这里有一些化式子技巧吗？

范德蒙恒等式

长这样：
$\sum_{i=0}^kC^i_nC^{k-i}_m$=$C^k_{n+m}(k<=min(n,m))$

有时候有惊喜，可以消去一个求和号。

考虑它的组合意义证明（转自acdreamers）

甲班有n个人，乙班有m个人，从两个班中选$k(k<=min(n,m))$个人有$C^{k}{n+m}$种选法，换一种方法，枚举从甲班中选$i$个人，从乙班中选$k-i$个，方案数是$\sum{i=0}^kC^i_nC^{k-i}_m$，所以他们是相等的。

这个考虑组合意义的想法很有用。

斯特林数

第一类斯特林数

不会告辞。

第二类斯特林数

可以用来化$m^n$一类的东西，我懒得抄了，直接挂链接：y2823774827y

生成函数

咕了！！！

多项式全家桶

多项式乘法（FFT/NTT)

全文背诵，大声熟练。

常用NTT模数表

多项式求导与积分

咕

多项式求逆

咕

多项式开根

咕

多项式求ln

咕

泰勒展开和牛顿迭代

不会

多项式exp

不会

多项式快速幂

不会

多项式除法

不会

u