5、排列数公式
排列数公式就是从n个不同元素中，任取m（m≤n）个元素（被取出的元素各不相同），按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。排列与元素的顺序有关，组合与顺序无关。加法原理和乘法原理是排列和组合的基础。
排列数:
从n个不同的元素中任取m(m≤n)个元素的所有排列的个数，叫做从n个不同的元素中取出m(m≤n)个元素的排列数。记作符号 。A是英文arrangement（排列）的第一个大写字母。
例如，从7个不同的元素中任取5个元素的排列数为 ，从10个不同的元素中任取7个元素的排列数为。
排列数公式
公式A是排列公式，从N个元素取M个进行排列（即排序）。
符号
C：组合数
A：排列数（在旧教材为P）
N：元素的总个数
M：参与选择的元素个数
!：阶乘，如5！=5×4×3×2×1=120
C：Combination 组合
P：Permutation排列 (现在教材为A-Arrangement)
推导过程
求排列数可以按依次填m个空位来考虑：假定有排好顺序的m个空位,从n个不同元素a1,a2,a3,…,an中任意取m个去填空,一个空位填1个元素，每一种填法就对应1个排列，因此，所有不同填法的种数就是排列数。
填空可分为m个步骤：
第1步，第1位可以从n个元素中任选一个填上，共有n种填法；
第2步，第2位只能从余下的n-1个元素中任选一个填上，共有n-1种填法；
第3步，第3位只能从余下的n-2个元素中任选一个填上，共有n-2种填法；
……
第m步，当前面的m-1个空位都填上后，第m位只能从余下的n-(m-1)个元素中任选一个填上，共有n-m+1种填法。
根据分步计数原理，全部填满m个空位共有n(n-1)(n-2)…(n-m+1)种填法。所以得到公式：
这里n，m∈N*，并且m≤n这个公式叫做排列数公式其中，公式右边第一个因数是n，后面的每个因数都比它前面一个因数少1，最后个因数为n-m+1，共有m个因数相乘。
排列数公式还可以写成：
注意：为了保证公式在n=m时成立，特规定0! =1。
示例：
在10个球中，任意取3个（不放回），求有多少种取法？
package action; public class demo2 { public static void main(String[] args) { // 在10个球中，取3个(不放回) System.out.println(f(10) / f(10 - 3)); } public static int f(int n) { if (n <= 1) return 1; return f(n - 1) * n; } }
附加1：矩阵相乘
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
小明最近在为线性代数而头疼，线性代数确实很抽象（也很无聊），可惜他的老师正在讲这矩阵乘法这一段内容。
当然，小明上课打瞌睡也没问题，但线性代数的习题可是很可怕的。
小明希望你来帮他完成这个任务。
现在给你一个ai行aj列的矩阵和一个bi行bj列的矩阵，
要你求出他们相乘的积（当然也是矩阵）。
(输入数据保证aj=bi,不需要判断)
输入格式
输入文件共有ai+bi+2行，并且输入的所有数为整数（long long范围内）。
第1行：ai 和 aj
第2~ai+2行：矩阵a的所有元素
第ai+3行：bi 和 bj
第ai+3~ai+bi+3行：矩阵b的所有元素
输出格式
输出矩阵a和矩阵b的积（矩阵c)
（ai行bj列）
样例输入
2 2 12 23 45 56 2 2 78 89 45 56
样例输出
1971 2356 6030 7141
package action; import java.io.IOException; import java.util.Scanner; public class demo2 { public static void main(String[] args) throws IOException { Scanner sc=new Scanner(System.in); String[] line1 = sc.nextLine().split(" "); int row1 = Integer.parseInt(line1[0]); int column1 = Integer.parseInt(line1[1]); int[][] m1 = new int[row1][column1]; for (int i = 0; i < m1.length; i++) { String[] data = sc.nextLine().split(" "); for (int j = 0; j < m1[i].length; j++) { m1[i][j] = Integer.parseInt(data[j]); } } String[] line2 = sc.nextLine().split(" "); int row2 = Integer.parseInt(line2[0]); int column2 = Integer.parseInt(line2[1]); int[][] m2 = new int[row2][column2]; for (int i = 0; i < m2.length; i++) { String[] data = sc.nextLine().split(" "); for (int j = 0; j < m2[i].length; j++) { m2[i][j] = Integer.parseInt(data[j]); } } sc.close(); int[][] result = new int[105][105]; for (int i = 0; i < row1; i++) { for (int j = 0; j < column2; j++) { for (int k = 0; k < row2; k++) { result[i][j] += m1[i][k] * m2[k][j]; } } } for (int i = 0; i < row1; i++) { for (int j = 0; j < column2; j++) { if (j == column2 - 1) { System.out.println(result[i][j]); } else { System.out.print(result[i][j] + " "); } } } } }
附加2：线性同余方程(B组以上)
数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次.
在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：
ax≡b (mod n)的方程。
此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。
这时，如果 x0 是方程的一个解，那么所有的解可以表示为：
{x0+kn/d|(k∈z)}
其中 d 是a 与 n 的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。
理论示例：
在方程3x ≡ 2 (mod 6)中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程无解。
在方程5x ≡ 2 (mod 6)中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一个解: x=4。
在方程4x ≡ 2 (mod 6)中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有两个解: x=2 and x=5。
代码示例：
青蛙的约会
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
输入
输入只包括一行5个整数x，y，m，n，L，
其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
输出
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
输入示例
1 2 3 4 5
输出示例
4
题目分析
设跳次数为t，则跳t次后两个青蛙的位置分别为(x+mt) mod L、(y+nt) mod L，相遇即是(x+mt)%L=(y+nt)%L转化为ax+by=c方程： (m-n)t+kL=y-x。设a=m-n，b=L，c=y-x，然后套用拓展欧几里得即可得出答案。
package action; import java.util.Scanner; // 求解同余方程的本质就是求线性方程 // 将求余方程转化为线性方程 public class demo2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long x = sc.nextInt(); // 坐标 long y = sc.nextInt(); // 坐标 long m = sc.nextInt(); // A第一次跳 long n = sc.nextInt(); // B第一次跳 long l = sc.nextInt(); // 维度总长 sc.close(); long a = m - n; long b = l; m = y - x; long d = 0; try { d = ExtGcd.linearEquation(a, b, m); } catch (Exception e) { System.out.println("Impossible"); } // 求解线性方程 long x0 = ExtGcd.x; b /= d; // 约一下 b = Math.abs(b); // 有可能小于0 /* =========这里是AC的关键=========== */ x0 = (x0 % b + b) % b; // 要求大于0的第一个解 System.out.println(x0); } // 私有的静态的内部类 private static class ExtGcd { static long x, y; public static long ext_gcd(long a, long b) { if (b == 0) { x = 1; y = 0; return a; } long res = ext_gcd(b, a % b); long x1 = x; x = y; y = x1 - a / b * y; return res; } public static long linearEquation(long a, long b, long m) throws Exception { long d = ext_gcd(a, b); if (m % d != 0) throw new Exception("无解"); long n = m / d; x *= n; y *= n; return d; } } }
