专栏文章

数学总结

AAhman_QwQ
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqytryw
此快照首次捕获于
2025/12/04 12:58
3 个月前
此快照最后确认于
2025/12/04 12:58
3 个月前
查看原文

论 数学

1.快速幂

‌快速幂算法是一种用于快速计算幂运算的算法，其时间复杂度为 O(log⁡n)O(\log n) ，其中 nn 为指数的位数。‌相比于传统的逐次相乘的方法，快速幂算法在指数很大的情况下优化效果更加明显。 快速幂算法的基本原理
快速幂算法通过将指数二进制的每一位与底数相乘来减少运算次数。例如，计算 21000000000210000000002100000000021000000000 时，普通的计算方法需要乘以 10000000001000000000 次，而快速幂算法只需要通过位运算和递归调用，将运算次数减少到 O(log⁡n)O(\log n) 。 快速幂算法的实现方式
快速幂算法可以通过多种方式实现，包括：
  1. 循环实现‌：通过循环遍历指数的二进制表示，逐位与底数相乘。
  2. 递归实现‌：将指数分成两半，递归计算一半的幂，然后根据指数的奇偶性决定是否乘以底数。
  3. 位运算实现‌：使用位运算判断指数的奇偶性，并逐步减少指数的值。

见此

CPP
int pow( int a, int b ) {
int r = 1, base = a;
while( b != 0 ) {
if( b & 1 )
r *= base;
base *= base;
b >>= 1;
}
return r;
}

P1226

2质数筛

基本定义及性质：
　　质数又称素数。一个大于 11 的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
　 在整个自然数集合中，质数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的质数大约有 Nln⁡NN \ln N 个,即每 ln⁡N \ln N 个数中有一个质数。
　 质数的判断：
　 有一个简单而又暴力的算法，即试除法， 即扫描 2∼N2 \sim \sqrt N 之间的所有整数，依次检查它们能否整除 NN 。
　 伪代码如下:
CPP
bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2;i <= sqrt(n);i++)
        if(n%i == 0) return false;
    return true;
}
　时间复杂度为： O（log n）O（log\ n）。
　 有一些效率更高的随机性算法，不过水平超出了我们的范畴，不再讨论。
　

　 质数的筛选：

　 质数的筛法有许多种，先来介绍一个最实惠常用的埃拉托色尼斯筛法吧。
　 我们可以从2开始， 由小到大扫描每个数x，它的倍数 2x，3x，....，[N/x] * x 标记为合数。
　 当扫描到一个数时，若它尚未被标记，则它不能被2~x - 1之间的任何数整除，该数就是质数。
　 伪代码如下：
CPP
void primes(int n)
{
    memset(vis, 0, sizeof(vis));
    for(int i = 2;i <= n;i++)
    {
        if(vis[i]) continue;
        printf("%d\n", i); //i是质数
        for(int j = i;j <= n/i;j++) vis[i*j] = 1;
    }
}
　 时间复杂度为：O（NloglogN）O（NloglogN） ；
　　该算法实现简单，效率已经非常接近于线性，是算法竞赛中最常用的质数筛法。
　　
　　再来介绍一种更优的算法：线性筛（欧拉筛法）
　　算法思想：通过从大到小累积质因子的方式标记每个合数，设数组 vv 记录每个数的最小质因子，我们按以下步骤维护 vv ；
　 1.依次考虑 2∼N2 \sim N 之间的每一个 ii .
　 2.若 v[i]=iv[i] = i , 说明 ii 是质数， 把它保存下来。
　 3.扫描不大于 v[i]v[i] 的每个质数， 令 v[i∗p]=pv[i*p] = p . 也就是在 ii 的基础上累积一个质因子 pp ，因为 p<=v[i]p <= v[i] ，所以 pp 就是合数 i∗pi*p 的最小质因子。
　　伪代码如下：
CPP
void primes(int n)
{
    memset(v, 0, sizeof(v));//最小质因子
    int m = 0;//质数数量
    for(int i = 2;i <= n;i++)
    {
        if(v[i] == 0)
        {
            v[i] = i;
            prime[++m] = i;//i是质数
        }
        //给当前的数i乘上一个质因子
        for(int j = 1;j <= m;j++)
        {
            // i有比prime[j]更小的质因子,或者超出n的范围,停止循环。
            if(prime[j] > v[i] !! prime[j] > n/i) break;
            //prime[j]是合数i*prime[j]的最小质因子
            v[i*prime[j]] = prime[j];
        }
    }
}

3.欧拉函数

欧拉函数 φ(n)\varphi(n) 是数论中的一个重要概念，它表示小于等于 nn 的正整数中与 nn 互质的数的数目。以下是关于欧拉函数的详细解释：
一、定义与性质
‌定义‌：欧拉函数 φ(n)\varphi(n) 是一个定义在正整数集上的函数，其值等于序列 0,1,2,…,n−10,1,2,…,n-1 中与 nn 互素的数的个数。
性质：
当 pp 是素数时，φ(p)=p−1\varphi(p)=p-1 。
欧拉函数是积性函数，但不是完全积性函数。
当且仅当 nn 可以分解成两个互质的整数之积 n=p1p2n = p_1 p_2 时， φ(n)=φ(p1p2)=φ(p1)φ(p2)\varphi(n) = \varphi(p1p2) = \varphi(p1)\varphi(p2) 。
当 n>2n>2 时， φ(n)\varphi(n) 都是偶数。
二、欧拉函数的应用
欧拉函数在数论中有着广泛的应用，特别是在密码学中的RSA算法中，欧拉函数起到了关键作用。在RSA算法中，需要选择两个大素数 pp 和 qq ，并计算它们的乘积 n=pqn=pq 作为模数。然后，利用欧拉函数计算 φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1) ，这是RSA算法中的一个重要参数。
三、欧拉函数前十项
由于欧拉函数的值取决于与n互质的数的个数，因此无法直接给出欧拉函数前十项的具体数值，因为每个n的值不同，φ(n)的值也会不同。但是，可以给出一些具体的例子：
φ(1)=1\varphi(1)=1 （因为 11 与 11 互质）
φ(2)=1\varphi(2)=1 （因为 11 与 22 互质）
φ(3)=2\varphi(3)=2 （因为 11 和 22 都与 33 互质）
φ(4)=2\varphi(4)=2 （因为 11 和 33 都与 44 互质）
... 以此类推。
四、欧拉公式与欧拉定理 ∗*
虽然欧拉函数与欧拉公式、欧拉定理在名称上相似，但它们在数学上是不同的概念。欧拉公式主要在复变函数和拓扑学中使用，而欧拉定理则涉及同余的性质。因此，在讨论欧拉函数时，应注意区分这些概念。
综上所述，欧拉函数是数论中的一个重要概念，具有独特的性质和应用价值。在研究和应用欧拉函数时，应深入理解其定义和性质，并熟练掌握其计算方法。
如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 Pollard Rho 算法优化。
CPP
#include <cmath>

int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}
对任意满足 gcd⁡(a,b)=1\gcd(a, b) = 1 的整数 a,ba,b ，有 φ(ab)=φ(a)φ(b)\varphi(ab) = \varphi(a)\varphi(b) 。
特别地，当 nn 是奇数时 φ(2n)=φ(n)\varphi(2n) = \varphi(n) 。
若 n=pkn = p^k ，其中 pp 是质数，那么 φ(n)=pk−pk−1\varphi(n) = p^k - p^{k - 1} 。
由唯一分解定理，设 n=∏i=1spikin = \prod_{i=1}^{s}p_i^{k_i} ，其中 pip_i 是质数，有 φ(n)=n×∏i=1spi−1pi\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}} 。
对任意不全为00 的整数 m,nm,n ，φ(mn)φ(gcd⁡(m,n))=φ(m)φ(n)gcd⁡(m,n)\varphi(mn)\varphi(\gcd(m,n))=\varphi(m)\varphi(n)\gcd(m,n) 。可由上一条直接计 算得出
还可以利用欧拉筛法求出多个欧拉函数。 伪代码如下：
CPP
void eular(int n)
{
    //数组phi 表示欧拉函数
    int cnt = 0;
    for(int i = 2;i <= n;i++)
    {
        if(v[i] == 0)
        {
            prime[++cnt] = i;phi[i] = i-1;
        }
        for(int j = 1;j <= cnt;j++)
        {
            if(prime[j]*i > n) break;
            v[prime[j]*i] = 1;
            if(i%prime[j] == 0)
            {
                phi[i*prime[j]] = phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]] = phi[i]*(prime[j]-1);
        }
    }
}

4.求gcd

‌求最大公约数（GCD）的方法有多种，常见的包括穷举法、辗转相除法（欧几里得算法）、质因数分解法和更相减损法。‌
  1. 穷举法‌是最直观的方法，通过列出两个整数的所有因数，找出最大的公约数。这种方法简单易理解，但当整数较大时，计算速度较慢。
    辗转相除法（欧几里得算法）‌通过不断将较大数除以较小数，取余数后再对两数进行同样的操作，直到余数为 00 ，此时的除数即为最大公约数。这种方法适用于大整数，计算速度快。
    ‌质因数分解法‌是将两个整数进行质因数分解，找出公共的质因数并相乘。这种方法适用于大整数，计算速度快，但步骤较为复杂。
    更相减损法‌是通过不断减去两个整数中的较小数，直到两数相等，此时的数为最大公约数。这种方法适用于奇数，但在整数较大时效率较低。
此外，还有一些高效的算法如Stein算法和二进制算法，这些方法利用位运算和递归来提高计算速度，特别适用于计算机实现。
CPP
#include<stdio.h>
int gcd(int m,int n){
	while(m%n!=0){
		int r=m%n;
		m=n;
		n=r;
	}
	return n;
}
int main(){
int m,n;
scanf("%d%d",&m,&n);
printf("%d\n",gcd(m,n));
return 0;
}
递归版
CPP
int gcd(int x,int y){return(y?gcd(y,x%y):x);}
扩展：
最小公倍数
LCM(x,y)=(x∗y)/gcd(x,y)LCM(x,y)=(x*y)/gcd(x,y)

5.费马小定理

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果 pp 是一个质数，而整数a不是p的倍数，则有 ap−1≡1（mod p）a^{p-1}\equiv 1（mod\ p） 。

应用 应用

注意：费马小定理只是素数判定的一个必要条件，素数一定满足费马小定理，满足费马小定理的数，却不一定是素数，例如Carmichael数（Carmichael数都是符合费马小定理的，但是他们都是合数）。
引理1：若 a，b，ca，b，c 为任意 33 个整数, mm 为正整数，且(m,c)=1(m,c)=1，则当 a×c≡b×c(mod m)a\times c \equiv b \times c(mod\ m) 时，有 a≡b(mod m)a \equiv b(mod\ m) 。
引理2：设mm是一个整数且 m>1m>1 ， bb 是一个整数且 gcd(m,b)=1gcd(m,b)=1 。如果 a1,a2,a3,a4,…ama_1,a_2,a_3,a_4,…a_m 是模m的一个完全剩余系，则 b⋅a1,b⋅a2,b⋅a3,b⋅a4,…b⋅amb·a_1,b·a_2,b·a_3,b·a_4,…b·a_m 也构成模m的一个完全剩余系。
费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理），中国剩余定理(又称孙子定理），费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况, 即 aφ(p)=ap−1≡1(mod p)a^{\varphi(p)}=a^{p-1} \equiv 1(mod\ p)
p3381 exmple:
CPP
#define ll long long
ll fpm(ll x, ll power, ll mod) {
    x %= mod;
    ll ans = 1;
    for (; power; power >>= 1, (x *= x) %= mod)
    	if(power & 1) (ans *= x) %= mod;
    return ans;
}
int main() {
	ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元
}

6.扩展欧几里得

扩展欧几里得算是欧几里得算法（辗转相除法）的扩展。它不仅能计算两个整数 aa 和 bb 的最大公约数，还能找到整数 xx 和 yy（其中一个可能是负数），使得 ax+by=gcd(a,b)ax + by = gcd(a, b) 。这个算法通过辗转相除法得到最大公约数，并通过收集相除法中产生的式子，倒推得到 ax+by=gcd(a,b)ax + by = gcd(a,b) 的整数解

扩展欧几里得算法的应用领域

扩展欧几里得算法在工程和数学领域有广泛应用。它常用于求解模线性方程及方程组，特别是在需要求解贝祖等式ax+by=gcd(a,b)ax + by = gcd(a, b)时，解一定存在。此外，扩展欧几里得定理还可以用于求解线性同余方程(见CRT）。
CPP
int exgcd(int a,int b,int &x,int &y){    
	int ret,tmp;
  	if(b==0){
    	    x=1;y=0;return a;
     	}
     	ret=exgcd(b,a%b,x,y);
        	tmp=x;x=y;y=tmp-a/b*y;
        	return ret;
 }

扩展欧几里得算法求逆元

使用辗转相除法求最大公约数‌：从 aa 和 bb 开始，逐步除以较大的数，取余数，直到余数为 00 ，此时的除数即为最大公约数。 ‌逆推求解‌：从求得的最大公约数开始，逐步逆推回原等式，得到 xx 和 yy 的值。如果最大公约数为 11 ，则 xx 即为 aa 模 pp 的逆元。
CPP
#include <iostream>
using namespace std;
 
// 扩展欧几里得算法求逆元
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, x, y);
    long long t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}
 
int main() {
    long long a, b, x, y;
    cin >> a >> b; // 读取a和b的值
    long long d = exgcd(a, b, x, y);
    if (d != 1) {
        cout << "无逆元" << endl;
    } else {
        // 输出模b的逆元
        cout << (x % b + b) % b << endl;
    }
    return 0;
}

线性求逆元

‌线性求逆元的方法可以通过递推公式实现，其时间复杂度为 O(n)O(n) 。‌ 逆元在模数运算中非常重要，特别是在计算组合数时，逆元可以将模乘转化为模加运算，从而简化计算。线性求逆元的基本思想是利用模运算的性质，通过递推公式快速计算 11 到 nn 的逆元。具体步骤如下 ：
递推公式‌：设 pp 为模数，对于任意整数 ii ，其逆元可以通过以下递推公式计算： inv[i]=(p−pi)⋅inv[p%i](modp)\text{inv}[i] = (p - \frac{p}{i})\cdot\text{inv}[p\% i] \pmod{p}
\hspace{2cm} 其中 inv\text{inv} =1=1 作为初始条件。‌
初始化和边界条件‌：首先将 inv\text{inv} 设置为 11 ，然后从 22 开始迭代计算直到 nn 。

7.中国剩余定理（孙子定理）（CRT）

见此
在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以 33 余 22 ），五五数之剩三（除以 55 余 33 ），七七数之 剩二（除以 77 余 22 ），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。
  1. 找出三个数，从 33 和 55 的公倍数中找出被 77 除余 11 的最小数 1515 ，从 33 和 77 的公倍数中找出被 55 除余 11 的最小数 2121 ，最后从 55 和 77 的公倍数中找出除 33 余 11 的最小数 7070 。
  2. 用 1515 乘以 22 （ 22 为最终结果除以 77 的余数），用 2121 乘以 33（ 33 为最终结果除以 55 的余数），同理，用 7070 乘以 22 （ 22 为最终结果除以 33 的余数），然后把三个乘积相加 15∗2+21∗3+70∗215∗2+21∗3+70∗2 得到和 233233 。
  3. 用 233233 除以 3，5，73，5，7 三个数的最小公倍数 105105 ，得到余数 2323 ，即 233mod  105=23233\mod 105=23 。这个余数 2323 就是符合条件的最小数。
即：
计算所有模数的积 nn ；
对于第 ii 个方程：
a.计算 mi=nnim_i=\frac{n}{n_i} ；
b.计算 mim_i 在模 nin_i 意义下的 逆元 mi−1m_i^{-1}；
c.计算 ci=mimi−1c_i=m_im_i^{-1}（不要对 nin_i 取模）。
方程组在模 nn 意义下的唯一解为：
x=∑i=1kaici(modn)x=\sum_{i=1}^k a_ic_i \pmod n
为使 n1+n2+n3n_1+n_2+n_3 的和作为“孙子问题”的一个最终解，需满足：
  1. n1n_1 除以 33 余 22 ，且是 55 和 77 的公倍数。
  2. n2n_2 除以 55 余 33 ，且是 33 和 77 的公倍数。
  3. n3n_3 除以 77 余 22 ，且是 33 和 55 的公倍数。
公式： 设正整数 m1,m2,...,mkm_1,m_2,...,m_k 两两互素，则同余方程组
x≡a1(mod m1)\hspace{2cm} x \equiv a_1(mod\ m_1)
x≡a2(mod m2)\hspace{2cm} x \equiv a_2(mod\ m_2)
x≡a3(mod m3)\hspace{2cm} x \equiv a_3(mod\ m_3)
⋅\hspace{3cm} \centerdot
⋅\hspace{3cm} \centerdot
⋅\hspace{3cm} \centerdot
x≡ak(mod mk)\hspace{2cm} x \equiv a_k(mod\ m_k)
有整数解。并且在模 M=m1⋅m2⋅m3⋅ ... ⋅mkM=m_1·m_2·m_3·\ ...\ ·m_k 下的解是唯一的，解为
x≡(a1M1M1−1+a2M2M2−1+...+akMkMk−1)mod Mx \equiv (a_1M_1M^{-1}_1+a_2M_2M^{-1}_2+...+a_kM_kM^{-1}_k)mod\ M
其中 Mi=M/miM_i=M/m_i \hspace{0.5cm} 而 Mi−1M^{-1}_i 是 MiM_i 模 mim_i 的逆元。

扩展：模数不互质的情况

两个方程
设两个方程分别是 x≡a1(modm1)x\equiv a_1 \pmod {m_1} 、 x≡a2(modm2)x\equiv a_2 \pmod {m_2} ；
将它们转化为不定方程： x=m1p+a1=m2q+a2x=m_1p+a_1=m_2q+a_2 ，其中 p,qp, q 是整数，则有 m1p−m2q=a2−a1m_1p-m_2q=a_2-a_1 。
由 裴蜀定理，当 a2−a1a_2-a_1 不能被 gcd⁡(m1,m2)\gcd(m_1,m_2) 整除时，无解；
其他情况下，可以通过 扩展欧几里得算法 解出来一组可行解(p,q)(p,q) ；
则原来的两方程组成的模方程组的解为 x≡b(modM)x\equiv b\pmod M ，其中 b=m1p+a1b=m_1p+a_1, M=lcm(m1,m2)M=\text{lcm}(m_1, m_2) 。
多个方程:
用上面的方法两两合并即可。

8.杨辉三角（组合数）

杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。

性质：

前提：每行端点与结尾的数为1. （与上图中的n不同，这里第一行定义为n=1）
  1. 每个数等于它上方两数之和。
  2. 每行数字左右对称，由1开始逐渐变大。
  3. 第 nn 行的数字有 nn 项。
  4. 前 nn 行共 (1+n)n/2(1+n)n/2 个数。
  5. 第 nn 行的 mm 个数可表示为 C(n−1，m−1)C(n-1，m-1) ，即为从 n−1n-1 个不同元素中取 m−1m-1 个元素的组合数。
  6. 第 nn 行的第 mm 个数和第 n−m+1n-m+1 个数相等 ，为组合数性质之一。
  7. 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第 n+1n+1 行的第 ii 个数等于第 nn 行的第 i−1i-1 个数和第 ii 个数之和，这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i−1)C(n+1,i)=C(n,i)+C(n,i-1) 。
  8. (a+b)n(a+b)n的展开式中的各项系数依次对应杨辉三角的第 (n+1)(n+1) 行中的每一项。
  9. 将第 2n+12n+1 行第 11 个数，跟第 2n+22n+2 行第 33 个数、第 2n+32n+3 行第 55 个数……连成一线，这些数的和是第 4n+14n+1 个斐波那契数；将第 2n2n 行第 22 个数 (n>1)(n>1) ，跟第 2n−12n-1行第 44 个数、第 2n−22n-2 行第 66 个数……这些数之和是第 4n−24n-2 个斐波那契数。
  10. 将第 nn 行的数字分别乘以 10m−110^{m-1} ，其中 mm 为该数所在的列，再将各项相加的和为 11(n−1)11^(n-1) 。
    110=1,111=1×100+1×101=11，112=1×100+2×101+1×102=121，113=1×100+3×101+3×102+1×103=1331，114=1×100+4×101+6×102+4×103+1×104=14641，115=1×100+5×101+10×102+10×103+5×104+1×105=16105111^0=1, 11^1=1 \times 10^0+1 \times 10^1=11， 11^2=1 \times 10^0+2 \times 10^1+1 \times 10^2=121，11^3=1 \times 10^0+3 \times 10^1+3 \times 10^2+1 \times 10^3=1331，11^4=1 \times 10^0+4 \times 10^1+6 \times 10^2+4 \times 10^3+1 \times 10^4=14641，11^5=1 \times 10^0+5 \times 10^1+10 \times 10^2+10 \times 10^3+5 \times 10^4+1×10^5=161051。
  11. 第 nn 行数字的和为 2n−12^{n-1} 。
    1=21−1，1+1=22−1，1+2+1=23−1，1+3+3+1=24−1，1+4+6+4+1=25−1，1+5+10+10+5+1=26−11=2^{1-1}，1+1=2^{2-1}，1+2+1=2^{3-1}，1+3+3+1=2^{4-1}，1+4+6+4+1=2^{5-1}，1+5+10+10+5+1=2^{6-1} 。
  12. 斜线上数字的和等于其向左（从左上方到右下方的斜线）或向右拐弯（从右上方到左下方的斜线），拐角上的数字。
    1+1=2，1+1+1=3，1+1+1+1=4，1+2=3，1+2+3=6，1+2+3+4=10，1+3=4，1+3+6=10，1+4=51+1=2，1+1+1=3，1+1+1+1=4，1+2=3，1+2+3=6，1+2+3+4=10，1+3=4，1+3+6=10，1+4=5 。
  13. 将各行数字左对齐，其右上到左下对角线数字的和等于斐波那契数列的数字。
    1，1，1+1=2，2+1=3，1+3+1=5，3+4+1=8，1+6+5+1=13，4+10+6+1=21，1+10+15+7+1=34，5+20+21+8+1=551，1，1+1=2，2+1=3，1+3+1=5，3+4+1=8，1+6+5+1=13，4+10+6+1=21，1+10+15+7+1=34，5+20+21+8+1=55 。

加法 & 乘法原理

加法原理

完成一个工程可以有 nn 类办法， ai(1≤i≤n)a_i(1 \le i \le n) 代表第 ii 类方法的数目。那么完成这件事共有 S=a1+a2+⋯+anS=a_1+a_2+\cdots +a_n 种不同的方法。

乘法原理

完成一个工程需要分 nn 个步骤， ai(1≤i≤n)a_i(1 \le i \le n) 代表第 ii 个步骤的不同方法数目。那么完成这件事共有 S=a1×a2×⋯×anS = a_1 \times a_2 \times \cdots \times a_n 种不同的方法。

排列数

从 nn 个不同元素中，任取 mm （ m≤nm\leq n ， mm 与 nn 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 nn 个不同元素中取出 mm 个元素的一个排列；从 nn 个不同元素中取出 mm ( m≤nm\leq n ) 个元素的所有排列的个数，叫做从 nn 个不同元素中取出 mm 个元素的排列数，用符号 Anm\mathrm A_n^m （或者是 Pnm\mathrm P_n^m ）表示。
排列的计算公式如下： Anm=n(n−1)(n−2)⋯(n−m+1)=n!(n−m)!\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
n!n! 代表 nn 的阶乘，即 6!=1×2×3×4×5×66! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 。
公式可以这样理解： nn 个人选 mm 个来排队 ( m≤nm \le n )。第一个位置可以选 nn 个，第二位置可以选 n−1n-1 个，以此类推，第 mm 个（最后一个）可以选 n−m+1n-m+1 个，得：
Anm=n(n−1)(n−2)⋯(n−m+1)=n!(n−m)!\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
全排列： nn 个人全部来排队，队长为 nn 。第一个位置可以选 nn 个，第二位置可以选 n−1n-1 个，以此类推得：
Ann=n(n−1)(n−2)⋯3×2×1=n!\mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n!
全排列是排列数的一个特殊情况。

组合数

从 nn 个不同元素中，任取 m≤nm \leq n 个元素组成一个集合，叫做从 nn 个不同元素中取出 mm 个元素的一个组合；从 nn 个不同元素中取出 m≤nm \leq n 个元素的所有组合的个数，叫做从 nn 个不同元素中取出 mm 个元素的组合数，用符号 (nm)\dbinom{n}{m} 来表示，读作「 nn 选 mm 」。
组合数计算公式 (nm)=Anmm!=n!m!(n−m)!\dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!}
如何理解上述公式？我们考虑 nn 个人选 mm 个出来（ m≤nm \le n ），不排队，不在乎顺序。如果在乎顺序那么就是 Anm\mathrm A_n^m ，如果不在乎那么就要除掉重复，那么重复了多少？同样选出来的 mm 个人，他们还要「全排」得 m!m! ，所以得： (nm)×m!=Anm(nm)=Anmm!=n!m!(n−m)!\begin{aligned} \dbinom{n}{m} \times m! &= \mathrm A_n^m\\ \dbinom{n}{m} &= \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!} \end{aligned}
组合数也常用 Cnm\mathrm C_n^m 表示，即 Cnm=(nm)\displaystyle \mathrm C_n^m=\binom{n}{m}。现在数学界普遍采用 (nm)\dbinom{n}{m} 的记号而非 Cnm\mathrm C_n^m 。
组合数也被称为「二项式系数」，下文二项式定理将会阐述其中的联系。
特别地，规定当 m>nm>n时， Anm=(nm)=0\mathrm A_n^m=\dbinom{n}{m}=0 。
排列公式： A(n,k)=n×(n−1)×⋯×(n−k+1)A(n,k)=n×(n−1)×⋯×(n−k+1)A(n,k)=n×(n−1)×⋯×(n−k+1)A(n,k)=n×(n−1)×⋯×(n−k+1) ，表示从 nn 个不同元素中取出 kk 个元素进行排列。
组合公式 C(n,k)=A(n,k)k!=n!k!(n−k)!C(n,k)=k!A(n,k)=k!(n−k)!n!C(n,k)=A(n,k)k!=n!k!(n−k)!C(n,k)=k!A(n,k)=k!(n−k)!n! ，表示从 nn 个不同元素中取出 kk 个元素的组合数。
例如，计算从 55个元素中取出 33 个元素的组合数： (53)=5!3!(5−3)!=5×4×3×2×1(3×2×1)×(2×1)=1206×2=10(35)=3!(5−3)!5!=(3×2×1)×(2×1)5×4×3×2×1=6×2120=10\dbinom{5}{3}=\frac{5!}{3!(5−3)!}=\frac{5 \times 4\times 3\times 2\times 1}{(3\times 2\times 1)\times (2\times 1)}=1206\times 2=10 (35)=3!(5−3)!5!=(3\times 2\times 1)\times (2\times 1)5\times 4\times 3\times 2\times 1=6\times 2120=10
因此，从 55 个元素中取出 33 个元素的组合数是 1010 。

code:

递归方法
递归方法通过枚举所有可能的组合。例如，从1到5中选择3个数的组合可以通过递归实现：
CPP
#include<iostream>
using namespace std;

void dfs(int u, int sum, int state) {
    if (u == k) {
        // 输出当前组合
        cout << "组合: ";
        for (int i = 0; i < n; i++) {
            if (state & (1 << i)) {
                cout << i + 1 << " ";
            }
        }
        cout << endl;
        return;
    }
    dfs(u + 1, sum + 1, state | (1 << u)); // 选择第u个数
    dfs(u + 1, sum, state); // 不选择第u个数
}

int main() {
    int n = 5, k = 3; // 从5个数中选择3个数
    dfs(0, 0, 0); // 调用递归函数
    return 0;
}
这种方法直观易懂，但效率较低，适用于小规模数。 递推预处理方法
递推预处理方法通过计算组合数的性质进行优化。例如，组合数满足递推关系：Cab=Cab−1+Cab−2C_a^b = C_a^{b-1} + C_a^{b-2} ，适用于中小规模数据：
CPP
void init_C() {
    int N = 100; // 预处理的最大下标
    vector<vector<int>> c(N + 1, vector<int>(N + 1, 0));
    for (int i = 0; i <= N; i++) {
        c[i] = c[i][i] = 1; // C_i^0 和 C_i^i 都为1
        for (int j = 1; j < i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P; // P为模数，防止溢出
        }
    }
}

扩展：Lucas定理

Lucas定理是用来求 C(n,m)mod  pC(n,m)\mod p ，pp 为素数的值。
Lucas定理：令 n=sp+q,m=tp+r(0≤q，r≤p−1)n=sp+q , m=tp+r (0 \le q ，r \le p-1)
(sp+qtp+r)=(st)(qr)(mod  p)\begin{pmatrix} sp+q \\ tp+r \end{pmatrix}=\dbinom{s}{t}\dbinom{q}{r} (\mod p ) 时间 O(log⁡p(n)∗p)O(\log_p(n)*p)
CPP
int Lucas (ll n , ll m , int p) 
{
  return m == 0 ? 1 : 1ll*comb (n%p , m%p , p) * Lucas (n/p,m/p,p)%p ;
}
//comb()函数中，因为q ， r < p , 所以这部分暴力完成即可。
//C++求C(n, m) mod 10007    版本二 要求p z在100000左右
ll f[N];
void init(int p) 
{       //f[n] = n!
    f[0] = 1;
    for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;
} 
ll pow_mod(ll a, ll x, int p)
{
    ll ret = 1;
    while (x)
        {
        if (x & 1)  ret = ret * a % p;
        a = a * a % p;
        x >>= 1;
    }
    return ret;
}
 
ll Lucas(ll n, ll k, int p)        //C (n, k) % p
{
     ll ret = 1;
     while (n && k) 
        {
        ll nn = n % p, kk = k % p;
        if (nn < kk) return 0;  //inv (f[kk]) = f[kk] ^ (p - 2) % p
        ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p;
        n /= p, k /= p;
     }
     return ret;
}
int main(void)
{
    init (p);
    printf ("%I64d\n", Lucas (n, m, p));
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...