题意分析

本题要求计算(N)个元素中选取(M)个元素的排列数(NPM)（即\(A_{N}^M = \frac{N!}{(N - M)!}\)）的最后一个非零数字。

解题思路

1.分析末尾非零数字的影响因素 一个数末尾的(0)是由因数(2)和(5)相乘得到的。要得到排列数\(\frac{N!}{(N - M)!}\)的最后一个非零数字，首先需要消除末尾的(0)，这就需要统计分子(N!)和分母((N - M)!)中因数(2)和(5)的个数。 可以通过自定义函数Calc来统计一个数(n)中包含因数(t)的个数。函数Calc的原理是利用递归，每次将(n)除以(t)，并累加商的值，直到(n)为(0)，即：

$Calc(n,t) =$ $\begin{cases} 0, & n = 0 \\ \frac{n}{t} + Calc(\frac{n}{t},t), & n \neq 0 \end{cases}$

2.消除末尾(0)后考虑其他因数的影响 消除末尾(0)后，排列数剩下的部分是由其他因数（如(3)、(7)、(9)等）以及剩余的(2)组成。 对于因数(3)、(7)、(9)，分别通过自定义函数cal来统计它们在(N!)和((N - M)!)中的个数差。函数cal中又调用了函数g，g函数用于统计一个数中满足特定条件（如大于等于某个数(t)）的数字情况，并且也采用了递归的方式，即：

$g(num,t) =$ $\begin{cases} 0, & num = 0 \\ \frac{num}{10} + (num \bmod 10 \geq t) + g(\frac{num}{5},t), & num \neq 0 \end{cases}$

$cal(num,t) =$ $\begin{cases} 0, & num = 0 \\ cal(\frac{num}{2},t) + g(num,t), & num \neq 0 \end{cases}$

已知(2)、(3)、(7)、(9)的幂次的个位数是有规律循环的。代码中定义了二维数组T来存储(2)、(3)、(7)、(9)的幂次的个位数的循环规律。例如，(2)的幂次的个位数按照(6,2,4,8)循环（对应(2^4,2^1,2^2,2^3)的个位数）。

3.计算最后非零数字 先比较因数(2)和(5)的个数，若因数(5)的个数大于因数(2)的个数，那么末尾非零数字就是(5)。 若因数(2)的个数大于因数(5)的个数，就根据统计得到的(2)、(3)、(7)、(9)的个数差，结合它们幂次个位数的循环规律，计算出它们对最后非零数字的贡献，最后将这些贡献相乘并取个位数，得到排列数的最后一个非零数字。

代码实现：

#include<cstdio>
#include<algorithm>
using namespace std;

const int T[][4]={
	{6,2,4,8},//2^4,2^1,2^2,2^3
	{1,3,9,7},//3^4,3^1,3^2,3^3
	{1,7,9,3},//7^4,7^1,7^2,7^3
	{1,9,1,9},//9^4,9^1,9^2,9^3
};

int N,M;

int Calc(int num,int t) {
	return num==0?0:(num/t+Calc(num/t,t));
}

int g(int num,int t) {
	return (num==0)?0:(num/10+(num%10>=t)+g(num/5,t));
}
int cal(int num,int t) {
	return num==0?0:(cal(num/2,t)+g(num,t));
}

int main() {
#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	while(scanf("%d %d",&N,&M)!=EOF) {
		int num2=Calc(N,2)-Calc(N-M,2);
		int num5=Calc(N,5)-Calc(N-M,5);
		if(num5>num2) {
			puts("5");
			continue;
		} else {
			int ans=1;
			int num3=cal(N,3)-cal(N-M,3);
			int num7=cal(N,7)-cal(N-M,7);
			int num9=cal(N,9)-cal(N-M,9);
			if(num2>num5)
				ans*=T[0][(num2-num5)%4],ans%=10;
			ans*=T[1][num3%4],ans%=10;
			ans*=T[2][num7%4],ans%=10;
			ans*=T[3][num9%4],ans%=10;
			printf("%d\n",ans);
		}
	}
	return 0;
}

🧠 题解（Solution）

✅ 本质分析：

我们要求的是：

𝑁 𝑃 𝑀

𝑁 ! ( 𝑁 − 𝑀 ) ! NPM= (N−M)! N! ​

即：

𝑁 𝑃 𝑀

𝑁 × ( 𝑁 − 1 ) × ⋯ × ( 𝑁 − 𝑀 + 1 ) NPM=N×(N−1)×⋯×(N−M+1) 我们不需要求出完整的数值，而是要得到其乘积的最后一个非零数字，这涉及到：

高精度问题（结果可能非常大）；

末尾零的来源是 $2 \times 5$ 的倍数；

我们可以在乘法的过程中去除每步结果中的 $0$，并只保留最后非零位即可。

🔍 核心做法（简洁模拟）：

我们用如下方式处理：

从 $i = N$ 到 $N - M + 1$，逐个累乘；

每一步乘完后去除所有末尾的 $0$（不断除以 $10$）；

为了避免溢出，可以保留结果的后几位（如最后 $5$ 位）即可；

最后输出结果的最后一个非零数字。

✅ 示例分析（如 $N = 10, M = 5$）：

计算：

10 × 9 × 8 × 7 × 6

30240 10×9×8×7×6=30240 末尾两个 $0$ 去掉，变成 $3024$，其最后一个非零数字是 4。

🧮 时间复杂度分析：

每个输入最多计算 $M$ 项，故单组输入复杂度为 $O(M)$；

由于 $N$ 最多为 $2 \times 10^7$，需注意优化；

可通过限制中间结果长度、用数组保存预处理、移除 $2$ 与 $5$ 因子的个数等方法进一步加速。

代码实现：

#include <iostream>
#include <cstdio>

using namespace std;

int r[] = {2, 4, 8, 6};

int f(int n)
{
	int ret = 0;
	while(n) {
		ret = (ret + n / 5) & 3;
		int tmp = 0;
		if(n % 5 == 2) tmp = 1;
		else if(n % 5 == 4) tmp = 2;
		ret = (ret + tmp) & 3;
		n /= 5;
	}
	return ret;
}

int main()
{
	int n, m;
	while(~scanf("%d%d", &n, &m))
		printf("%d\n", n <= 1 || m == 0 ? 1 : r[(3 + f(n) - f(n - m)) & 3]);
	
	return 0;
}