『置顶』【学习笔记】数学小知识点 upd2018.10.16

 

一、线性求逆元

1.1~n的逆元

    单独一个数\(\mod 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 pk\rfloor,ki+r\equiv 0(\mod p)\),

    那么等式两边同乘\(i^{-1}\cdot r^{-1}\),

    得到\(kr^{-1}+i^{-1}\equiv 0(\mod p)\)。

    移项可得\(i^{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!~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;
}

 

二、卡特兰数

    卡特兰数是求由\(n\)个\(0\)和\(n\)个\(1\)组成的\(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)\)个数有\(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\)的序列有多少个”,这个答案显然是\(C_{2n}^{n-1}\)。而映射回去这就是卡特兰数中不合法的方案,再拿包含\(n\)个\(0\)和\(n\)个\(1\)的串的方案\(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\not|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 ne)^n$$

 

五、Baby Step,Giant Step

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

 

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

 

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

 

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

 

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);
}

 

?、玄学

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