Java教程

清北灵堂送走记 Day2

本文主要是介绍清北灵堂送走记 Day2,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

清北灵堂送走记 \(Day2\)

前言

数论专题,鬼知道我这三天经历了什么

同余

若 \(a,b\) 为两个整数,且他们的差 \(a-b\) 能被某个自然数 \(m\) 所整除,则称 \(a\) 和 \(b\) 关于 \(m\) 同余,记作 \(a \equiv b \pmod m\)。它意味着 \(a-b = m \times k\)。

​ 一些性质:

  • 若 \(a \equiv b \pmod m\),则 \(a + c \equiv b + c \pmod m\)。

  • 若 \(a \equiv b \pmod m\),则 \(a \times c \equiv b \times c \pmod m\)。

  • 若 \(a \equiv b \pmod m, c \equiv d \pmod m\),则 \(a \times c \equiv b \times d \pmod m\)。

  • 若 \(a \equiv b \pmod m\) ,则 \(a^x \equiv b^x \pmod m\) 。

  • 若 $a \times b \bmod m $ 则 $ a \bmod m \times b \bmod m$ 。

  • 若 \(a \bmod p = x, a \bmod q = x\),且 \(p,q\) 互质,则 \(a \bmod (p \times q) = x\)。

    (感谢梓苏的友情赞助)

欧几里得算法(辗转相除法)

一条性质:\(z \mid x\),\(z | y\),则 \(z \mid (y-x)\),显然。

对于减法,设 \(y=kx+b\),则我们需要减 \(k\) 次,但是发现最后的 \(b\) 完全可以用取模取出来的。

所以得到了 $Gcd(a,b)=Gcd(b,a\bmod b) $

int Gcd(int a,int b){return !b?a:Gcd(b,a%b);}

如果又有某个毒瘤卡你,让你每次取模的 \(b\) 都恰好小于 \(x\) ,复杂度在 \(\log\) 级别,单次最坏复杂度 \(\mathcal{O(\log{V})}\)。

扩展欧几里得算法

定理:如果任意整数 \(a\) 和 \(b\) 都不为 \(0\),则 \(\gcd(a,b)\) 是 \(a\) 与 \(b\) 的线性组合集\({ax+by,a \in Z,b \in Z}\)中的最小正元素。

我们先证一下这个定理。

证明:设 \(s\) 是线性组合集中的最小正元素,则 \(s=ax+by\) ,再设 \(q=\lfloor \frac{a}{c} \rfloor\),则 \(a \bmod s = a-q \cdot s = a - q(ax+by)=a(1-qx)+b(-qy)\),所以\(a \bmod s\) 也是 \(a\) 与 \(b\) 的线性组合,由 \(s\) 为最小正元素,则 \(a \bmod s\)一定为零,同理可证 \(b \bmod s\)也为零,则 \(s\) 是 \(a\) 和 \(b\) 的公约数,则 $ s \le \gcd(a,b)$,又因为 \(s\) 是 \(a,b\) 的线性组合,则 \(gcd(a,b) \mid s\) ,则 \(gcd(a,b) \le s\) ,所以 \(s=\gcd(a,b)\)。

int Exgcd(int a,int b,int &x,int &y){
    if(!b){x=1,y=0;return a;}
    int res=Exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y;
    return res;
}

由上面飞鼠斐蜀定理可知,\(ax+by=gcd(a,b)\) 一定有解。根据欧几里得算法,\(\gcd(a,b)=gcd(b,a \bmod b)\),所以(一把子式子):

\(\because a{x}_1+b{y}_1=\gcd(a,b),b{x}_2+(a \bmod b){y}_2=gcd(b,a \bmod b)\)

\(\because \gcd(a,b)=\gcd(b,a \bmod b)\)

\(\therefore a{x}_1+b{y}_1=b{x}_2+(a \bmod b){y}_2\)

将 \(\bmod\) 用除法表示,则

\(\therefore a{x}_1+b{y}_1=b{x}_2+(\lfloor\frac{a}{b}\rfloor \cdot b){y}_2\)

\(\therefore a{x}_1+b{y}_1=a{y}_2+b({x}_2 - \lfloor\frac{a}{b}\rfloor \cdot {y}_2)\)

当 \(b=0\) 时,一定有 \(x=1,y=0\) ,递归回去即可,于是有了上面代码。

\(Exgcd\) 是可以求多解的,感谢 \(Konnyaku\) 的深情讲解。

思路来源不明,但是正确的((((

\(a(x_0+\frac{b}{\gcd(a,b)})+b(y_0-\frac{a}{\gcd(a,b)})=ax_0+by_0\)

显然把第一个式子化出来是和第二个式子等价的,但是为什么要\(\frac{b}{gcd(a,b)}\) 和 \(\frac{a}{\gcd(a,b)}\)呢?因为这俩玩意是令原式成立的最小的整数,证明不会,但显然是对的,因为你换个数显然不能全部包含所有解,话糙理不糙

所以 \(x\) 的通解是 \(x+ \frac{b}{\gcd(a,b)} \times t,t \in Z\)

逆元

乘法逆元 - BlackDan - 博客园

推销自己博客不过分吧。

质数筛

从娃娃时我们就学筛质数

for(int i=2;i<=sqrt(x);i++) if(!(x%i)) return 0;

复杂度为 \(\mathcal{O(n\sqrt{n})}\)

而后学的是埃筛,就是筛到一个数,把他的倍数全干掉喽。

void Is_prime(int n){
    memset(vis,true,sizeof vis);
    for(int i=2;i<=n;i++){
        if(!vis[i]) continue; 
        for(int j=i*i;j<=n;j+=i)
            vis[j]=false;
    }
}

有兴趣可以看复杂度怎么证明,反正我没兴趣Eratosthenes筛法时间复杂度分析_Gavin_Nicholas

大概是\(\Omega{(n\log\log n)}-\mathcal{O(n\log n)}\)?

有的时候毒瘤出题人卡你俩 \(\log\) ,所以我们有线性的欧拉筛。

int tmp[MAXN], Cnt = 0;
bool vis[MAXN];
void Init(int limit) {
    for(int i = 2; i <= limit; ++i) {
        if(!vis[i]) tmp[++ Cnt] = i;
        for(int j = 1; j <= Cnt && i * tmp[j] <= limit; ++j) {
            vis[i * tmp[j]] = true;
            if(i % tmp[j] == 0) break;
            // 欧拉筛每次都用最小质因子去筛每一个数
            // 在这里,因为 i 里面有 tmp[j] 这个因子,所以对于后面的 i * tmp[k] 来说
            // 可以拆成 i/tmp[j] * tmp[j] * tmp[k],而 tmp[j] < tmp[k]。
            // 所以要 break;
        }
    }
}

再次感谢梓苏

求解模线性方程

模线性方程即为\(ax \equiv b(\bmod n)\) 对 \(x\) 进行求解。

定理:方程 \(ax+by=c\) 与方程 \(ax \equiv c(\bmod b)\) 是等价的,有整数解的充要条件是 \(\gcd(a,b) \mid c\)

第 \(1\) 眼大雾,第 \(2\) 眼还是大雾,第 \(3\) 眼依然大雾

证明一下,对于一个模线性方程\(ax \equiv b(\bmod n)\),设\(q=ax \bmod n=b \bmod n\),则有\(ax=k_1n+q,b=k_2n+q(k_1.k_2 \in Z)\),两项作差得,\(ax-b=n \cdot(k_1-k_2)\) ,移项得 \(ax-n(k_1-k_2)=b\) ,令 \(y= -(k_1-k_2)\),式子为 \(ax+ny=b\),这玩意怎么这么眼熟?草,斐蜀定理,所以使式子有解要满足 \(\gcd(a,n) \mid b\),证毕。

那这玩意?扩欧搞出一组 \(ax+by=gcd(a,b)\) 的解。

两遍同时除以 \(\gcd(a,b)\) 再乘上 \(c\) 即可。

bool Co_eq(int a,int b,int c,int &x,int &y){
    int t=Exgcd(a,b,x,y);
    int k=c/t;
    if(!(c%t)) return false;
    x*=k;y*=k; return true;
}

中国剩余定理(Chinese remainder theorem、CRT)

鸣谢中国剩余定理(CRT)-知乎

引入都见过

《孙子算经》:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”

​ 化成式子就是这个样子 \(\begin{cases} x \equiv 2(\bmod 3) \\ x \equiv 3(\bmod 5) \\ x \equiv 2(\bmod 7) \end{cases}\)

一个整数除以3余2、除以5余3、除以7余2,求这个整数。
答案:23
解法:由于除以3余2,因此加上一个140;由于除以5余3,因此加上一个63;由于除以7余2,因此加上一个30;这三个数的和是140+63+30=233,再减去210,就得到了23了。
这么说吧,只要是除以3余了一个1,就加上一个70;只要是除以5余了一个1,就加上一个21;只要是除以7余了一个1,就加上一个15。然后累加。超过了106就减去105就行了。

当然你可以手算这个,那数大了呢,式子多了呢?

中国剩余定理登场了,老祖宗发明的,嘿。

一个问题:计算一个整数 \(x\) ,使得它满足除以 \(3\) 余 \(2\) 、除以 \(5\) 余 \(3\) 、除以 \(7\) 余 \(2\) 。

如果能够找到三个整数 \(x_1,x_2,x_3\) 使得:

​ \(\begin{cases} x_1 \equiv 2(\bmod 3),x_1 \equiv 0(\bmod 5),x_1 \equiv 0(\bmod 7) ①\\ x_2 \equiv 0(\bmod 3) ,x_2 \equiv 3(\bmod 5),x_2 \equiv 0(\bmod 7) ②\\ x_3 \equiv 0(\bmod 3),x_3 \equiv 0(\bmod 5),x_1 \equiv 2(\bmod 7) ③ \end{cases}\)

令 \(x=x_1+x_2+x_3\),易得

​ \(\begin{cases} x \equiv 2(\bmod 3) \\ x \equiv 3(\bmod 5) \\ x \equiv 2(\bmod 7) \end{cases}\),

称 \(x_1,x_2,x_3\) 为问题 \(①②③\) 的解,看出三个问题的本质事类似的。

对于问题 \(1-1\) 继续分解,如果能找到一个整数 \(y_1\) 满足

​ \(\begin{cases}y_1 \equiv 1(\bmod 3) \\ y_1 \equiv 0(\bmod 5) \\ y_1 \equiv 0(\bmod 7) \end{cases}\)

那么令 \(x_1=2 \cdot y_1\),很显然这样的 \(x_1\) 满足 \(1-1\),所以我们扩展问题,定义新三个问题为

​ \(\begin{cases} y_1 \equiv 1(\bmod 3),y_1 \equiv 0(\bmod 5),y_1 \equiv 0(\bmod 7) ①-①\\ y_2 \equiv 0(\bmod 3) ,y_2 \equiv 1(\bmod 5),y_2 \equiv 0(\bmod 7) ①-②\\ y_3 \equiv 0(\bmod 3),y_3 \equiv 0(\bmod 5),y_1 \equiv 1(\bmod 7) ①-③ \end{cases}\)

这三个问题的本质是相同的,如果找到了 \(y_1,y_2,y_3\) ,那么就可以取 \(x=2 \times y_1+3 \times y_2+ 2 \times y_3\)。

以问题 ①-① 为例,就是寻找一个整数 \(z\) 使得

​ \(\begin{cases}z \equiv 1(\bmod 3) \\ z \equiv 0(\bmod 5) \\ z \equiv 0(\bmod 7) \end{cases}\).

于是 \(z\) 一定是 \(5 \times 7=35\) 的倍数,假设 \(z=35k\) ,则有 \(35k \equiv 1(\bmod 3)\),这 \(k\) 是什么?就是 \(5 \times 7 \bmod 3\) 的逆元,将这个 \(k\) 记作\([35^{-1}]_{3}\),那此时 \(z\) 就等于 \(5 \times 7 \times [(5 \times 7)^{-1}]_{3}\),恰好就是 \(5 \times 7 \times 2=70\),对应了上面的解法中的 \(70\) 。

以此类推,问题①-②的解答就是 \(3 \times 7 \times [(3\times7)^{-1}]_5\),恰好就是 \(3 \times 7 \times 1=21\)

问题①-③的解答就是 \(3 \times 5 \times [(3 \times 5)^{-1}]_7\),恰好就是 \(3 \times 5 \times 1=15\),都与上面对应。

所以将问题的分解复原,可得:

\(x=2 \times (5 \times 7 \times [(5 \times 7)^{-1}]_{3})+3 \times(3 \times 7 \times [(3\times7)^{-1}]_5)+2 \times (3 \times 5 \times [(3 \times 5)^{-1}]_7)\)

最后注意到 \(x+3 \times 5 \times 7\)也满足条件,因此要计算最小负整数,只需要 \(sum \bmod (3 \times 5 \times 7)\) 即可。

如果有多组解满足条件呢?他们之间又有什么联系?

假设 \(X,Y\) 都满足 “除以 \(3\) 余 \(a\)、除以 \(5\) 余 \(b\)、除以 \(7\) 余 \(c\) ”。观察发现 \(X-Y\) 满足 “除以 \(3\) 余 \(0\) 、除以 \(5\) 余 \(0\) 、除以 \(7\) 余 \(0\)”。因此 \(X-Y\) 一定是 \(105\) 的倍数,也就是说在模 \(105\) 的意义下,通过分解,组合解答的 \(x\) 恰是唯一解。

把这个问题一般化:假设整数 \(m_1,m_2,…,m_n\) ,且两两互质,则对于任意 \(a_1,a_2,…,a_n\),方程组:

​ \(\begin{cases}x \equiv a_1(\bmod m_1) \\ x \equiv a_2(\bmod m_2) \\……\\ x \equiv a_3(\bmod m_3)\\\end{cases}\)

都存在整数解,若 \(X,Y\) 同时满足该方程组,必有 \(X \equiv Y(\bmod N)\),其中 \(N=\prod_{i=1}^{n}m_i\)

具体而言,将上面过程表示成式子即:

\(x \equiv \displaystyle \sum_{i=1}^{n}{a_i \times \frac{N}{m_i} \times [(\frac{N}{m_i})^{-1}]_{m_i}}(\bmod N)\)

int Exgcd(int a,int b,int &x,int &y){
    if(!b){x=1;y=0;return a;}
    int Gcd=Exgcd(b,a%b,x,y);
    int t=x;
    x=y;y=t-a/b*y;
    return Gcd; 
}
signed main() {
   n=read();int Mul=1;
   for(int i=1;i<=n;i++){
       M[i]=read();Mul*=M[i];Y[i]=read();
   }
   for(int i=1;i<=n;i++){
       int qwq=Mul/M[i];
       int x=0,y=0;
       Exgcd(qwq,M[i],x,y);
       Ans+=Y[i]*qwq*(x>=0?x:x+M[i]);
   }
   return print(Ans%Mul),0;
}

套式子来就行,注意变量别混了就行。

扩展中国剩余定理(Extended Chinese remainder theorem,EXCRT)

鸣谢扩展中国剩余定理讲解-Yang1208

鸣谢扩展中国剩余定理详解-自为风月马前卒

我们知道中国剩余定理用来求解同于方程组必须要求模数互质,但是如果某个啥币出题不让他们互质呢?

自为风月马前卒:“把出题人吊起来干一顿。”

\(CRT\) 和 \(EXCRT\) 其实没多少关系,一个用 \(Exgcd\) ,另一个是构造。

先列出这一把子方程 \(\begin{cases}x \equiv x_1(\bmod m_1) \\x \equiv x_2(\bmod m_2) \\……\\ x \equiv x_3(\bmod m_3)\\\end{cases}\)

我们选择上面俩看看能不能合成,于是得到下面一个方程组 \(\begin{cases}x = x_1+k_1 \times m_1 \\x=x_2+k_2 \times m_2\end{cases}\)

我们的到了一个等式:\(x_1+k_1\times m_1=x_2+k_2 \times m_2\) ,移项得到 \(k_1 \times m_1 +(-k_2) \times m_2=x_2-x_1\),是不是 \(ax+by=c\) 的形式?自然阔欧搞上,我们用扩欧求出 \(k_1\) 的通项,但是根据扩欧的限制条件,必须有\(gcd(m_1,m_2) \mid (x_2-x_1)\) ,如果前提不满足,则这个同余方程组无解。我们设 \(K_1,K_2\) 为 \(K_1 \times m_1 +(-K_2) \times m_2=\gcd(m_1,m_2)\)的两个特解,将式子两边都乘上 \(\frac{x_2-x_1}{\gcd(m_1,m_2)}\),就知道上述式子 \(k_1=K_1 \times \frac{x_2-x_1}{\gcd(m_1,m_2)},k_2=K_2 \times \frac{x_2-x_1}{gcd(m_1,m_2)}\),带回去,得到:

​ \(\begin{cases}x = x_1+K_1 \times \frac{x_2-x_1}{\gcd(m_1,m_2)} \times m_1 \\x=x_2+ K_2 \times \frac{x_2-x_1}{\gcd(m_1,m_2)} \times m_2\end{cases}\)

显然满足这个方程组的\(K_1,K_2\)不只一组,并且每一组\(K_1,K_2\)都对应一个 \(x\),所以我们能知道每两个解\(\Delta\)就是 \(\frac{(x_2-x_1)}{gcd(m_1,mod_2)}\times m_1\) 和\(\frac{(x_2-x_1)}{\gcd(m_1,m_2)}\times m_2\)的倍数,所以 \(\Delta\) 一定是 \(\frac{m_1\times m_2}{\gcd(m_1,m_2)}\) 的倍数,即 \(\Delta\) 是 \(lcm(m_1,m_2)\) 的倍数。

感谢梓苏的讲解。为什么呢,设有 \(K_1\) 和 \(K^{'}_{1}\) ,带入一式,得到两式作差,\(\Delta x= (k_1-k_{1}^{'}) \times \frac{(x_2-x_1)}{gcd(mod_1,mod_2)}\times m_1\) ,得到 \(\Delta\) 是 $ \frac{(x_2-x_1)}{gcd(mod_1,mod_2)}\times m_1$的倍数,同理得到 $ \Delta $ 也是 \(\frac{(x_2-x_1)}{\gcd(m_1,m_2)}\times m_2\) 的倍数。

所以每两个解 $ \Delta $ 一定是\(\frac{m_1\times m_2}{gcd(m_1,m_2)}\)的倍数,那\(\frac{m_1\times m_2}{gcd(m_1,m_2)}\)就是\(lcm(m_1,m_2)\),所以 $ \Delta$ 一定是 \(lcm(m_1,m_2)\) 的倍数。

又因为$ x=k_1\times m_1+x_1\(,这样我们就将上面两个同余方程合成为\)x \equiv k_1\times m_1+x_1(\bmod lcm(m_1,m_2))$。

完事,

费马小定理

内容:若 \(p\) 为质数, \(\gcd(a,p)=1\) ,则\(a^{p-1} \equiv 1 (\bmod p)\)

证明自行百度,其实是我不会。

徐佬给出了解释,我们来看他怎么说:

欧拉定理

实质上是对费马小定理的拓展。

内容:若正整数 \(a,p\) 互质,则 \(a^{\varphi(n)} \equiv 1(\bmod n)\)

证明自行百度,梓苏也不会了。,给个\(Link\)欧拉-费马小定理定理(定理证明)

推论:若 \(a,n\) 互质,则对于任意正整数 \(b\) ,有 \(a^b \equiv a^{b \bmod \varphi(n)} \bmod n\)

证明一下,设 \(b=q \times \varphi(n)+r,0 \le r \le \varphi(n)\),则 \(r=b \bmod \varphi(n)\)。前方高能

\(a^b=a^{q \cdot \varphi(n)+r} \equiv (a^{\varphi(n)})^{q} \times a^r \equiv 1^q \times a^r \equiv a^r \equiv a^{b \bmod \cdot \varphi(n)}(\bmod n)\)

这式子很明白了吧。

扩展欧拉定理:

\(a^b \equiv a^{b \bmod \varphi(n)+\varphi(n)} (\bmod n)\),当 \(a,n\) 不一定互质且 \(b \ge \varphi (n)\)

\(a^b \equiv a^{b} (\bmod n)\),当 \(a,n\) 不一定互质且 \(b < \varphi (n)\)

证明详解这里,我太菜了,不会证,梓苏说记住就行?

【数论数学】扩展欧拉定理一扶苏一

附赠一个小推论:

推论:若正整数 \(a,n\) 互质,则满足 \(a^x \equiv 1(\bmod n)\) 的最小正整数 \(x_0\) 是 \(\varphi(n)\) 的约数

欧拉函数

定义:\(1-N\) 中与 \(N\) 互质数的个数叫欧拉函数,记 \(\varphi(N)\)

对 \(N\) 进行质因数分解 $N=p_1^{c_1} \times p_2^{c_2} \times … \times p_k^{c_k} $

则有 $\varphi(N)=N \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2}) \times…\times (1-\frac{1}{p_k}) $

特别的\(\varphi(1)=1\)

证明:要求的就是 \(1-N\) 中与 \(N\) 不含相同质因子的数,我们先假设 \(N\) 只有两个质因子,假设 \(p,q\) 为 \(N\) 的质因子,那么 \(1-N\) 中 \(p\) 的倍数有\(\frac{N}{p}\),同理 \(q\) 有 \(\frac{N}{q}\) 个,我们自然要筛掉这些数,但是其中 \(q \times p\) 被筛了两次,所以还要加回来,得 \(N-\frac{N}{p}-\frac{N}{q}+ \frac{N}{pq}\),对式子稍作变换,得 \(N \times (1-\frac{1}{p}-\frac{1}{q}-\frac{1}{pq})\),再变得 \(N \times (1-\frac{1}{p}) \times (1-\frac{1}{q})\),然后我们采用数学归纳法类推到多项就得到上面式子。

实现:

①求单个欧拉函数,类似质数判断

根据上面函数定义式,可以得到一个在分解质因数的同时求解单个欧拉函数的方法,时间复杂度 \(\mathcal{O(\sqrt{n})}\)

int Get_phi(int x){
    int res=x;
    for(int i=2;i*i<=x;i++)
    if(!(x%i)){res=res/i*(i-1);while(!(x%i)) x/=i;}
    if(x>1) res=res/x*(x-1);
    return res;
}

②递推打表,类似埃式筛

void Phi(int n){
    for(int i=1;i<=n;i++) phi[i]=i;
    for(int i=1;i<=n;i++){
        if(!phi[i]) continue;
        for(int j=i;j<=n;j+=i)
        phi[j]=phi[j]/i*(i-1);
    }
}

③线性筛,类似欧拉筛质数

需要用到欧拉函数的两个性质

若有 \(p \mid N\),且满足 \(p^2 \mid N\),则 \(\varphi(N)=\varphi(\frac{N}{p}) \times p\).

证明:若有 \(p\mid N\),且满足 \(p^2 \mid N\),说明 \(N\) 和 \(N/p\) 有相同的质因子,我们分析只含两个质因子的简单情况,

\(\varphi(N)=N-\frac{N}{p}-\frac{N}{q}+ \frac{N}{pq}\),\(\varphi(N/p)=\frac{N}{p}-\frac{N}{p^2}-\frac{N}{pq}+ \frac{N}{p^2q}\),二者相除商为 \(p\),

若有 \(p \mid N\),且一定不满足 \(p^2 \mid N\),则 \(\varphi(N)=\varphi(\frac{N}{p}) \times (p-1)\).

证明:若有 \(p\mid N\),且满足 \(p^2 \mid N\),说明 \(N\) 和 \(N/p\) 一定互质,根据积性函数定义有 \(\varphi(N)=\varphi(N/p) \times \varphi(p)\),因为 \(p\) 为质数,则 \(\varphi(p)=p-1\)(费马小定理),得\(\varphi(N)=\varphi(\frac{N}{p}) \times (p-1)\),证毕。

void Phi(int n){ phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]) Prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*Prime[j]<=n;j++){
            vis[i*Prime[j]]=true;
            if(!(i%Prime[j])){ phi[i*Prime[j]]=phi[i]*Prime[j];}
            //说明i*Prime[j]中含有两个Prime[j]的因子,应用推论1
            else phi[i*Prime[j]]=phi[i]*phi[Prime[j]];//反之推论2
        }
    }
}

组合数

组合数-BlackDan

再推销一波博客(✿◡‿◡)

多重集合的排列

\(M={k_1\cdot a_1,k_2 \cdot a_2 ,…k_n \cdot a_n}\), \(a_i\) 为不同元素, \(k_i\) 为个数。

多重集合 \(M=\left \{k_{1}\cdot a_{1},k_{2}\cdot a_{2},\cdots ,k_{n}\cdot a_{n}\right \}\) 的 \(r\) 排列数为 \(k^{r}\)

多重集合 \(M=\left \{k_{1}\cdot a_{1},k_{2}\cdot a_{2},\cdots ,k_{n}\cdot a_{n}\right \}\)的全排列数为:\(\frac{\left ( k_{1}+k_{2}+\cdots +k_{n}\right )!}{k_{1}!k_{2}!\cdots k_{n}!}\)

多重集合部分有限部分无限分母仅除有限部分阶乘乘。

一个例子:在 \(1-n\) 之间随机生成长度为 \(n\) 的整数序列,请问正好含有 \(n-1\) 个不同的整数的方案数,答案\(\bmod 1e9+7\)。

\(Ans= C_{n}^{n-1} \times (n-1) \times \frac {n!} {2!} \bmod 1e9+7\)

先从 \(n\) 个数里面选 \(n - 1\) 个数,对于剩下一个位置可以是这 \(n-1\) 个数的任意一个,\(n\) 个数随便排列,但是有两个重复元素,注意对 \(2!\) 求逆元。

二项式定理

定理:\((a+b)^n= \displaystyle \sum_{r=0}^{n}C^{r}_{n}a^{n-r}b^{r}\)

这就是二项式定理,等式右边即为 \((a+b)^n\) 的二项式,共有 \(n+1\) 项。

\(C^{r}_{n}a^{n-r}b^{r}\) 叫做二项式展开式的第 \(r+1\) 项,也就是通项,通项用 \(T_{r+1}\) 表示。

\(T_{r+1}=C^{r}_{n}a^{n-r}b^{r}\),\(C^r_n(t=0,1,2…n)\) 叫做 \(r+1\) 项的二项式系数。

证明:组合证明法

将幂次拆开, \((a+b)^n=(a+b) \cdot (a+b) … (a+b)\)

按照乘法分配律展开,直到无括号。因为每项都可以选 \(s\) 或者 \(b\) ,因此共有 \(2^n\) 项,显然所有项都是\(a^{n-r}b^r(r=0,1,2…,n)\) 的形式,为了计数形如\(a^{n-r}b^r\) 的项的系数,必须从 \(n\) 个 \(a+b\) 中选取 \(n-r\) 个 \(a\) (从而乘机中其余的 \(r\) 个项都是 \(b\)),所以 \(a^{n-r}b^{r}\) 的系数是 \(C^{n-r}_{n}=C_{n}^{r}\),证毕。

P1313:二项式定理,快速幂,费马小定理,逆元

卢卡斯定理(Lucas's theorem)

对于非负整数 \(m,n\) 和质数 \(p\),\(C_m^n \equiv \displaystyle \prod_{i=0}^{k} C_{m_i}^{n_i}(\bmod p)\)

\(m=m_kp^k+…+m_1p+m_0,n=n_kp^k+…+n_1p+n_0\) 是 \(m,n\) 的 \(p\) 进制展开。

但其实我们常用这个可以与之互推的式子:

\(C_m^n=C_{m \bmod p}^{n \bmod p} \cdot C_{\lfloor \frac{m}{p}\rfloor}^{\lfloor \frac{n}{p}\rfloor} (\bmod p)\),当 \(m<n\) 时,规定 \(C_m^n=0\)

我们可以利用这个式子递归求解,递归边界就是 \(n=0\)。其实只需要记住公式就够了,因为你可以马上写出卢卡斯的板子。

int C(int m,int n,int p){
	return m<n?0:fact[m]*inv(fact[m],p)%p*inv(fact[m-n],p)%p;
}
int lucas(int m,int n,int p){
	return !n?1:lucas(m/p,n/p,p)*C(m%p,n%p,p)%p;
}

证明:设 \(x\)是任意小于 \(p\) 的正整数,那么:\(C_p^x=\frac{p!}{x!(p-x)!}=\frac{p\cdot(p-1)!}{x \cdot (x-1)! \cdot (p-x)!} =\frac{p}{x} \cdot C_{p-1}^{x-1}\),由于 \(x<p\) 且 \(p\) 是质数,所以存在 \(x\) 模 \(p\) 意义下的逆元,故:\(C_p^x \equiv p \cdot inv(x) \cdot C_{p-1}^{x-1}(\bmod p)\),显然右边是 \(p\) 的倍数,所以 \(C_{p}^{x} \equiv 0(\bmod p)\),由二项式定理:$(1+x)^n= \displaystyle \sum_{i=0}{n}C_{n}{i} x^{i} $,由于 \((1+x)^p=\displaystyle \sum_{i=0}^{p}C_p^i\) 除了 \(i=0\) 和 \(i=p\) 的项外模 \(p\) 都为零(上面已证),所以 \((1+x)^p \equiv 1+x^p (\bmod p)\),现在我们设 \(\begin{cases} \lfloor \frac{m}{p}\rfloor=q_m \\ \lfloor \frac{n}{p} \rfloor =q_n \\ \end{cases}\), \(\begin{cases} m \bmod p=r_m\\ n \bmod p=r_n \\ \end{cases}\),那么那么 \(\begin{cases}m=q_mp+r_m \\ n=q_np+r_n\\ \end{cases}\),再由二项式定理 \((a+b)^m= \displaystyle \sum_{k=0}^{m}C^{k}_{m}x^{k}\),而同时有(前方高能):\((1+m)^x=(1+x)^{q_mp+r_m}=(1+x)^{q_mp} \cdot (1+x)^{r_m}=[(1+x)^p]^{q_m} \cdot (1+x)^{r_m} \equiv (1+x^p)^{q_m} \cdot (1+x)^{r_m}= \displaystyle \sum_{i=0}^{q_m} C_{q_m}^{i}x^{ip} \sum_{j=0}^{r_m}C_{r_m}^{j}x^{j} = \sum_{i=0}^{q_m} \sum_{j=0}^{r_m} C_{q_m}^{i}C_{r_m}^{j} x^{ip+j} (\bmod p)\)。注意满足 \(j>m_r\) 的项为 \(0\),所以上面和式一定遍历所有可能的非零项,我们再枚举 \(k=ip+j\),得到 \((1+x)^m \equiv \displaystyle \sum_{k=0}^{m}C_{q_m}^{\lfloor k/p\rfloor}C_{q_m}^{k \bmod p}x^k(\bmod p)\),为什么呢?和梓苏讨论了一会,是这样的:\(\displaystyle \sum_{i=0}^{q_m}\sum_{j=0}^{r_m}\) 能使 \(ip+j\) 遍历到的范围是 \(0\) 到 \(q_mp+r_m=m\) ,即换元之后枚举的 \(\displaystyle \sum_{k=0}^{m}\),根据二项式定理的结果,得 \(\displaystyle \sum_{k=0}^{m}C_m^kx^k \equiv \sum_{k=0}^{m}C_{q_m}^{\lfloor k/p\rfloor}C_{q_m}^{k \bmod p}x^k(\bmod p)\),对比系数,则,\(C_m^k \equiv C_{q_m}^{\lfloor\frac{k}{p}\rfloor}\cdot C_{r_m}^{k \bmod p}=C_{q_m}^{q_k}\cdot C_{r_m}^{r_k}(\bmod p)\),令 \(k=n\),得到 \(C_m^n=C_{m \bmod p}^{n \bmod p} \cdot C_{\lfloor \frac{m}{p}\rfloor}^{\lfloor \frac{n}{p}\rfloor} (\bmod p)\),定理得证。

扩展卢卡斯定理

扩展卢卡斯定理-OI Wiki

自行解决,我累了。

后记

经过这几天的经历,充分的告诉了我一个事实:只有交了钱的自学最有效率!

这金牌真tm ssh??

这篇关于清北灵堂送走记 Day2的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!