清北灵堂送走记 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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程