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

点击量:171

 

一、线性求逆元

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\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 ne)^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\)值就可以了。

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

六、组合问题

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

当小球遇上盒子

    如果已知\(C_n^m\),可以递推出\(C_n^{m+1}\),因为根据计算式,\(C_n^m=\frac{n!}{m!(n-m)!},C_n^{m+1}=\frac{n!}{(m+1)!(n-m-1)!}\)。因此\(C_n^{m+1}=C_n^m\cdot \frac{n-m}{m+1}\),或\(C_n^m=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)\),反正很快。

    但是在noip级别的比赛中,用内建函数是不保险的,这时我们如果要\(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;改成i>=0;即可)

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\ \mathrm{and}\ m=m\),那么\(C_n^m\)为奇数,否则为偶数。

3
说点什么

avatar
2 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
nonamewjyyywjy Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
wjy
游客
wjy

看了王聚佬的博客,收获满满!

noname
游客

Orz

/* */