数学小知识点【学习笔记】 upd on 2019.7.10

点击量：1325

一、线性求逆元

1. $1\sim n$ 的逆元

单独一个数 $\bmod p$ 的逆元是可以用费马小定理($p$ 为质数)或 exgcd 在 $O(\log p)$ 的复杂度内求的。但是如果要求 $1\sim n$ 的逆元，其实用不到 $O(n\log n)$。正如 $O(n)$ 的线筛和 $O(\sqrt{n})$ 的单独质数判断一样，逆元也是可以递推的。

要求 $i$ 在 $\mod p$ 意义下的逆元，我们假设 $1\sim i-1$ 的乘法逆元全部已知。

设 $p=ki+r$，且 $k=\lfloor \frac pi\rfloor,ki+r\equiv 0(\mod p)$，
那么等式两边同乘 $i^{-1}\cdot r^{-1}$，
得到 $kr^{-1}+i^{-1}\equiv 0(\mod p)$。
移项可得 $i^{-1}\equiv -kr^{-1}(\mod p)$。这样在求出来后取最小正整数值就可以了。

Code：

#include<cstdio>
#include<cstring>
long long inv[3000001];
int main()
{
    inv[1]=1;
    puts("1");
    int n;
    long long p;
    scanf("%d%lld",&n,&p);
    for(int i=2;i<=n;++i)
    {
        inv[i]=((-(p/i)*inv[p%i])%p+p)%p;
        printf("%lld\n",inv[i]);
    }
    return 0;
}

2. $1!\sim n!$ 的逆元

阶乘的逆元也是可以递推的。

$$(i+1)!^{-1}=\frac{1}{(i+1)!}\ (i+1)!^{-1}\cdot (i+1)=\frac {1}{i!}=i!^{-1}\ \Rightarrow i!^{-1}=(i+1)!^{-1}\cdot (i+1)$$

Code：

#include<cstdio>
long long inv(long long x,long long p)
{
    long long y=p-2;
    long long ans=1,m=x;
    while(y)
    {
        if(y&1)
            ans=ans*m%p;
        m=m*m%p;
        y>>=1;
    }
    return ans;
}
long long Inv[10000];
int main()
{
    int n,p;
    scanf("%d%d",&n,&p);
    long long frac=1;
    for(int i=1;i<=n;++i)
        frac=frac*i%p;
    Inv[n]=inv(frac,p);
    for(int i=n-1;i;--i)
        Inv[i]=Inv[i+1]*(i+1)%p;
    for(int i=1;i<=n;++i)
        printf("%lld\n",Inv[i]);
    return 0;
}

3. 离线求逆元

这个方法也适用于求 $1\sim n$ 的逆元，并且更好记。

对于给定的 $n$ 个数 $a_1,a_2,\ldots,a_n$，我们需要在 $O(n)$ 的时间复杂度内求出它们关于 $p$ 的逆元。

借用求 $1!\sim n!$ 逆元的方法，令 $sum[i]$ 表示 $\prod_{j=1}^i a_j$。然后用快速幂在 $O(\log p)$ 的时间内求出 $sum[n]$ 的逆元，记作 $invsum[n]$。因此 $invsum[i]=\frac{1}{\prod_{j=1}^ia_j}$，是可以递推的，即 $invsum[i]=invsum[i+1]\times a_{i+1}$。

对于每个单独的数，$inv[i]=invsum[i]\times sum[i-1]$。

二、卡特兰数

卡特兰数是求由 $n$ 个 $0$ 和 $n$ 个 $1$ 组成的 $\mathrm C_{2n}^{n}$ 个串中，对于所有前缀都满足 $0$ 的个数不小于 $1$ 的个数的串的数量。

卡特兰数可以用来求解形如 NOIp2003 栈这样的题目。不过我们要求这个数 $Cat_n$ 应该怎么办呢？

有一种 DP 思路可以用来解决“栈”这个问题，得到的答案也是卡特兰数，但是时间复杂度是 $O(n^2)$ 的。我们需要找到卡特兰数的一个通项。

其中一种求法：
设一个由 $n$ 个 $0$ 和 $n$ 个 $1$ 组成的串不满足对于所有前缀，$0$ 的个数不小于 $1$ 的个数。则一定存在一个最小的非负整数 $k$，使得前 $2k+1$ 中有 $k$ 个 $0$ 和 $k+1$ 个 $1$。那么后面的 $2n-(2k+1)$ 个数有 $\mathrm C_{2n-2k-1}^{n-k}$ 种组合。而我们知道，第 $2k+1$ 个位置一定是 $1$ 打破了这个规律，因为前面的 $2k$ 个数都满足条件，因此方案为 $Cat_k$。所以
$$
tmp=\sum_{i=1}^{n-1}Cat_i\cdot C_{2n-2i-1}^{n-i}
$$
表示了不合法情况的种类数，用总数减去它就是
$$
Cat_n=C_{2n}^n-\sum_{i=1}^{n-1}Cat_i\cdot C_{2n-2i-1}^{n-i}
$$
不过这样还是 $O(n^2)$ 的。

另一种求法：
还是设一个由 $n$ 个 $0$ 和 $n$ 个 $1$ 组成的串不满足对于所有前缀，$0$ 的个数不小于 $1$ 的个数。则一定存在一个最小的非负整数 $k$，使得前 $2k+1$ 个数中有 $k$ 个 $0$ 和 $k+1$ 个 $1$。我们把后面从 $2k+2$ 开始每一位都取反，能得到唯一一个包含 $n-1$ 个 $0$ 和 $n+1$ 个 $1$ 的串。

对于任意一个包含 $n-1$ 个 $0$ 和 $n+1$ 个 $1$ 的串，一定可以找到一个最小的 $m$，使得前 $2m+1$ 个数中有 $m$ 个 $0$ 和 $m+1$ 个 $1$。我们此时把这个串的 $2m+2$ 以后都取反，得到一个包含 $n$ 个 $0$ 和 $n$ 个 $1$ 的串，且存在 $0$ 的个数小于 $1$ 的个数的前缀。因为我们使用了取反操作，所以这里两组关系都是一一对应的。

而在知道它们的关系是一一对应的之后，原本不好求的方案如果转化成第二种求法会直接变成“有 $n-1$ 个 $0$ 和 $n+1$ 个 $1$ 的序列有多少个”，这个答案显然是 $\mathrm C_{2n}^{n-1}$。而映射回去这就是卡特兰数中不合法的方案，再拿包含 $n$ 个 $0$ 和 $n$ 个 $1$ 的串的方案 $\mathrm C_{2n}^n$ 减去它，就得到了

$$
Cat_n=C_{2n}^n-C_{2n}^{n-1}
$$

化简得

$$
Cat_n=\frac{(2n)!}{(n!)^2}-\frac{(2n!)}{(n-1)!(n+1)!}=\frac{C_{2n}^{n}}{n+1}
$$

三、线性求欧拉函数

欧拉函数 $\varphi(x)$ 表示 $1\sim x$ 之间有多少个数 $i$ 满足 $\gcd (i,x)=1$。那么对于质数 $p$ 当然有$\varphi(p)=p-1$，对于非质数，朴素算法可以在 $O(\sqrt{x})$ 的时间内求出单个数 $x$ 的欧拉函数 $\varphi(x)$。

而欧拉函数是积性的，如果 $\gcd (x,y)=1$，那么 $\varphi(xy)=\varphi(x)\varphi(y)$，因为它们没有共同的约数，所以乘起来后的数的约数个数自然也要乘起来（这不是严格证明

我们可以通过唯一分解定理来推导欧拉函数的计算式。设 $x=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$，那么

$$
\varphi(x)=x\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \cdots \times \frac{p_k-1}{p_k}=x\times \prod_{i=1}^m (1-\frac 1p)
$$

使用容斥原理可以证明这一点，任取 $x$ 的两个质因子 $p_i,p_j,i\not=j$。那么 $1\sim x$ 中为 $p_i$ 倍数的有 $\frac{x}{p_i}$ 个，为 $p_j$ 倍数的有 $\frac{x}{p_j}$ 个。为 $p_ip_j$ 倍数的有 $\frac{x}{p_ip_j}$ 个，再把它们加回来。这样答案就是 $x-\frac{x}{p_i}-\frac{x}{p_j}+\frac{x}{p_ip_j}=x(1-\frac{1}{p_i})(1-\frac{1}{p_j})$。

——摘自《算法竞赛进阶指南》

由此我们可以在线筛的时候完成欧拉函数的计算。
1. 如果 $i$ 是质数，那么 $\varphi(i)=i-1$；
2. 如果质数 $p|i$，可以知道 $\varphi(i\times p)=\varphi(i)\times p$。这个可以用反证法证明（或者感性理解吧，不是很会证）；
3. 如果质数 $p\nmid i$，那么满足积性函数 $\varphi(i\times p)=\varphi(i)\times\varphi(p)=\varphi(i)\times(p-1)$。

Code：

for(int i=2;i<=x;++i)
{
    if(is[i])
    {
        phi[i]=i-1;
        pri[++cnt]=i;
    }
    for(int j=1;j<=cnt&&i*pri[j]<=x;++j)
    {
        is[i*pri[j]]=0;
        if(i%pri[j]==0)
        {
            phi[i*pri[j]]=pri[j]*phi[i];
            break;
        }
        else
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
    }
}

四、斯特林公式

斯特林公式可以用来取一个数阶乘的近似值，而且在这个数很小时，斯特林公式也很精确。

证明需要用到数列和极限（？？？），反正不会证，咕掉。记结论好了。

$$
n!\approx \sqrt{2\pi n}(\frac n{\mathrm{e}})^n
$$

五、Baby Step,Giant Step

这是一种求满足 $a^x\equiv b\pmod m$ 的最小正整数 $x$ 的算法，时间复杂度为 $\sqrt{m}$。

有点像分块的思想，因为这里把指数分成了 $\sqrt{m}$ 组，每组 $\sqrt{m}$ 个，我们只需要预处理出固定的一组 $\sqrt{m}$ 个就可以通过 hash 判断是否相等。因此严格时间复杂度还要加上 hash 的常数。

令 $t=\left\lceil\sqrt{m}\right\rceil$，使 $x=i\times t-j,i\in \mathbb{N^*},0\le j < t$，则 $a^{i\times t-j}\equiv b\pmod m$，可得 $a^{i\times t}\equiv b\times a^j\pmod m$。

而我们知道 $j\in [0,t)\le \sqrt{m}$，所以可以预处理出 $b\times a^j\mod p$ 的存在性，放入 hash 表中。接着枚举 $i$，然后到哈希表中去匹配，找到最小的 $x$ 值就可以了。

学了 exBSGS 后我写了 BSGS&exBSGS 学习笔记，应该会更详细一些。

Code：

struct node
{
    long long n,p;//分别存原来的值
    node *nxt;
    node(long long n,int p)
    {
        this->n=n;
        this->p=p;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
}head[100003],*tail[100003];//hash表大小为100003
long long A,a,b,m;
long long up=ceil(sqrt(m));
long long tmp;
for(int i=0;i<up;++i)
{
    tmp=qmul(A,b);//快速乘,A是a^i
    tail[tmp%100003]->nxt=new node(tmp,i);
    tail[tmp%100003]=tail[tmp%100003]->nxt;
    A=A*a%m;
}
long long bs=qpow(b,t);
long long c=bs;
for(int i=1;i<=up;++i)
{
    node *p=&head[c%100003];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(p->n==c)
            ans=min(ans,up*i-p->p);//p->p即为j
    }
    c=qmul(c,bs);
}

六、组合问题

没总结出来什么东西，推得也没有别人好，先附上洛谷日报的一个链接，讲的挺不错的。

当小球遇上盒子

如果已知 $\mathrm C_n^m$，可以递推出 $\mathrm C_n^{m+1}$，因为根据计算式，$\mathrm C_n^m=\frac{n!}{m!(n-m)!},\mathrm C_n^{m+1}=\frac{n!}{(m+1)!(n-m-1)!}$。因此 $\mathrm C_n^{m+1}=\mathrm C_n^m\cdot \frac{n-m}{m+1}$，或 $\mathrm C_n^m=\mathrm C_n^{m-1}\cdot \frac{n-m-1}{m}$。

七、$\tt popcount$

对于单独一个数 $x$，它的 $\tt popcount$ 求解上界是 $O(\log x)$，只需要看它减到 $0$ 调用了多少次 $\tt lowbit$。
内建函数(g++里的) $\tt __builtin_popcount()$ 会比较快，近似 $O(1)$，反正很快。

但是在 NOI 系列的比赛中，是不能使用内建函数的，这时我们如果要 $O(1)$ 求出 $\tt popcount$ 怎么办呢？实际上当 $x$ 的上界不大时，我们可以用 $O(\max x)$ 来预处理出这些数的 $\tt popcount$。以前我都是$O(n\log n)$预处理的啊啊啊啊

我们要求一个数的 $\tt popcount$，只需要知道 $\tt {popcount}(x/2)$ 和 $x$ 的奇偶性就可以得到 $\tt {popcount}(x)$ 了。

for(int i=1;i<=10000000;++i)
    ppc[i]=ppc[i>>1]+(i&1);

八、二进制枚举子集

我们知道，要枚举 $\tt 111111_{(2)}$ 这样的数的子集时，可以直接循环 $[0,2^6-1]$，因为这里的全集刚好是连续的。那么当全集不连续时，形如 $\tt 101101_{(2)}$ 的子集，难道只能搜索吗？我们当然不愿意写搜索，因为比较耗时，我们有一种循环枚举的方式，可以刚好在子集个数的时间内枚举出 $s$ 的所有非空子集。（要枚举全部子集的话把 i; 改成在函数内部 break; 即可）

for(int i=s;i;i=s&(i-1))
    //do something

因为我们默认上述 $s$ 为非负整数，所以 $i$ 也都是非负整数，我们来看 $i-1$ 对 $i$ 这个数有什么影响。设 $\text{lowbit}(i)$ 位于 $i$ 的第 $k$ 位，那么 $i-1$ 的第 $[0,k-1]$ 位都是 $1$，而做了与运算后，$i-1$ 的 $[0,k-1]$ 位变得和 $s$ 一样了，只是第 $k$ 位变成了 $0$，之后枚举到高位时，这一位又会变成 $1$。所以这一过程枚举了二进制数 $s$ 的所有子集，时间复杂度为 $O(2^{\tt popcount(s)})$。

九、异或前缀和

对于 $n=2^k-1(k\ge 2)$，$\bigoplus\limits_{i=1}^n=0$。原因是每一个二进制位均出现了 $2^{k-1}$ 次 $1$。

首先考虑第 $k-1$ 位，显然当 $i\in[2^{k-1},2^k-1]$ 时，第 $k-1$ 位均为 $1$。而分别在 $[1,2^{k-1}-1],[2^{k-1},2^k-1]$ 中的后一半，第 $k-2$ 位均为 $1$，可以很容易地得到 $2^k-1(k\ge 2)$ 的异或前缀和为 $0$。

推广到一般，算到 $2^k$ 时，前缀和就是 $2^k$，接着是 $2^k\bigoplus (2^k+1)=1$，然后 $1\bigoplus(2^k+2)=2^k+3$，$(2^k+3)\bigoplus(2^k+3)=0$……

感觉发现了循环，实际上打表也能发现这个规律，记异或前缀和为 $sum[i]$，则

$$
sum[i]=\left\{\begin{matrix}
i&,i\equiv 0\pmod 4 \\
1&,i\equiv 1\pmod 4 \\
i+1&,i\equiv 2\pmod 4 \\
0&,i\equiv 3\pmod 4\\
\end{matrix}\right.
$$

这里有更严谨的证明 – Mychael，不过实在想不到了可以打表

十、欧拉函数与 $n$ 的关系

有一个结论是
$$
\sum_{d|n}\varphi(d)=n
$$

令 $f(n)=\sum_{d|n}\varphi(d)$，则对于 $f(nm)=\sum_{d|nm}\varphi(d)$ 且 $n\bot m$，因为 $n,m$ 互质，所以 $nm$ 的约数是从原来 $n,m$ 的约数中各取一个相乘构成的，而欧拉函数是积性函数，$\varphi(i)\varphi(j)=\varphi(ij)$，所以 $f(nm)=\left(\sum_{d|n}\varphi(d)\right)\times\left(\sum_{d|m}\varphi(d)\right)$，可以把它想象成一个多项式卷积。

$f(n)$ 是积性函数证毕。下证 $f(n)=n$。

考虑质数幂 $p^k,k\in[1,+\infty]$，则由定义 $f\left(p^k\right)=\sum_{d|p^k}\varphi(d)$，则函数值为
$$
\begin{aligned}&\varphi(1)+\varphi(p)+\varphi(p^2)+\dots+\varphi(p^k)\\=&(p-1)+p(p-1)+\dots+p^{k-1}(p-1)\\=&1+(p-1)\frac{1-p^k}{1-p}-1\\=&p^k\end{aligned}
$$
（等比数列求和再加 $\varphi(1)$）。

又因为 $f(n)$ 是积性函数，所以根据质数幂处的函数值可以知道全部的函数值，因此 $f(n)=n$。

十一、组合数奇偶性

如果 $n\ \mathrm{and}\ m=m$，那么 $\mathrm C_n^m$ 为奇数，否则为偶数。

用 Lucas 定理模 $2$ 可以推知。

十二、模数为质数的二次剩余

不给出证明，毕竟在 NOI 前几天学的。证明可以看这里 二次剩余学习笔记 – L_0_Forever_LF。

这个算法只能求解 $p$ 为奇质数的情况；需要特判 $p=2$ 才能解决所有 $p$ 为质数的问题，$\sqrt{a}=\left\{\begin{aligned}1,a\equiv 1\pmod 2\\0,a\equiv 0\pmod 2\end{aligned}\right.\pmod 2$。

要求 $a$ 在模 $p$ 意义下的二次剩余，即找到一个或所有满足 $x^2\equiv a\pmod p$ 的 $x$。

若 $a^{\frac{p-1}2}\equiv -1\pmod p$，说明 $a$ 没有模 $p$ 意义下的二次剩余。

若 $a\equiv 0\pmod p$ 即 $p|a$，说明 $a$ 的二次剩余为 $0$。

否则 $a^{\frac{p-1}2}\equiv 1\pmod p$。

此时在 $[0,p)$ 中随机一个整数 $b$，使得 $(b^2-a)$ 没有二次剩余，即 $(b^2-a)^{\frac{p-1}2}\equiv -1\pmod p$。这样的 $b$ 有 $\frac{p-1}2$ 个，因此可以在 $O(1)$ 的时间内找到这样的数。

定义 $\omega=\sqrt{b^2-a}$，答案就是 $(b+\omega)^{\frac{p+1}2}$。把复数运算稍微魔改一下就可以了。

由于 $(p-x)^2=p^2-2px+x^2\equiv x^2\pmod p$，所以二次剩余有两个，$x$ 和 $p-x$。

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

例题