洛谷刷题：P1009 [NOIP1998 普及组] 阶乘之和

用户11039529

发布于 2024-08-17 08:14:00

600

发布于 2024-08-17 08:14:00

文章被收录于专栏：算法学习日常

前言：

分享一题最近刷到的一个综合性较高的题，将高精度乘法和高精度加法都结合了起来

该题我用的是二维数组，我认为的一种适合新手的写法

关于高精度，我有以下文章，适合没有接触过高精度或者想复习高精度的读者，该文章包含高精度加法、减法、乘法、除法：

高精度原理介绍及代码实现_高精度代码-CSDN博客

题目：

P1009 NOIP1998 普及组阶乘之和

题目链接：

[NOIP1998 普及组] 阶乘之和 - 洛谷

题目分析：

该题的关键词有两个： 1、阶乘 2、和

再看一下该题的数据范围：

1≤ n ≤50

n最大可以取到50，除非python，C++这样子的计算是吃不消的，这样子要用到高精度

题目解法：

1、一维数组

A：存 i 的数组，因为高精度都需要将数字逆序存储为数组才能计算，A数组就是用来存 i 的数组

2、存各个阶乘的二维数组

jc i ：

jc i : 表示 i 的阶乘

3、存答案的二维数组

最终答案为ansn

初阶AC代码

const int N = 1005;

// a*b=c
int A[N];//i
int jc[N][N];//阶乘数组
int ans[N][N];//答案数组

int main()
{
	int n;
	cin >> n;
	jc[0][0] = 1;//0的阶乘 = 1
	int len_a = 1, len_b = 1, len_c = len_a + len_b, len_ans;
    // len_a: A数组的长度，也就是数字i转化为数组后，有几位数
    // len_b: 上一个数的阶乘的长度 
    // len_c: 当前阶乘的长度
    // len_ans: ans的长度

	jc[1][0] = 1; // 1的阶乘就是1
	ans[1][0] = 1;// 当n = 1时，答案就是1的阶乘：1
	for (int i = 2; i <= n; i++)
	{
		//得到i的数组:A
		int temp = i;
		len_a = 0;
		for (int j = 0; temp; j++)
		{
			A[j] = temp % 10;
			temp /= 10;
			len_a++;
		}

		//高精度乘法:求阶乘（i * (i - 1)!）
        // 也就是jc[i - 1] * A
		len_c = len_b + len_a;
		for (int j = 0; j < len_a/*i的长度*/; j++)
		{
			for (int k = 0; k < len_b/*上一个阶乘的长度*/; k++)
			{
				jc[i][j + k] += A[j] * jc[i - 1][k];//i * (i - 1)!
				jc[i][j + k + 1] += jc[i][k + j] / 10;
				jc[i][j + k] %= 10;
			}
		}
		while (jc[i][len_c - 1] == 0)
			len_c--; // 去掉前置0

		len_b = len_c;//更新阶乘长度

		//高精度加法：求答案（ans[i] = ans[i-1] + jc[i]）
		len_ans = max(len_ans, len_c);
		for (int j = 0; j < len_ans; j++)
		{
			ans[i][j] += ans[i - 1][j] + jc[i][j];
			ans[i][j + 1] += ans[i][j] / 10;
			ans[i][j] %= 10;
		}
		if (ans[i][len_ans])
			len_ans++;

	}

	for (int i = 0; i < len_ans; i++)//逆序输出答案
		cout << ans[n][len_ans - 1 - i];
	return 0;
}

进阶版（空间复杂度减小）：

// 因为 i! = i * (i - 1)! ，所以要存i - 1的阶乘，每个阶乘的答案是一个数组，而要存上一级的答案，
// 要么用二维数组存1 ~ n的每个数的阶乘（上一种解法），要么只存这个数和上一个数的数组

int A[100];// 当前数

int B[100];// 上一个阶乘的答案 --------------- 优化部分，不需要用jc[][]来存每个数的阶乘了，只需要用到上一个的数的阶乘

int C[100];// 该数的阶乘
int ans[52][100];// 答案
int len_a, len_b, len_ans, len_c;

void solve()
{
	int n;
	cin >> n;
	ans[0][0] = 1;
	ans[1][0] = 1;
	len_ans = 1;

	B[0] = 1;
	len_b = 1;
	for (int i = 2; i <= n; i++)
	{
        // 注意将A、C给重新置为全0，否则进行高精度乘法+=时，会出现问题
		memset(C, 0, sizeof(C));
		memset(A, 0, sizeof(A));

		int temp = i;
		int j, k;
		for (j = 0; temp; j++)
		{
			A[j] = temp % 10;
			temp /= 10;
		}
		len_a = j;

		len_c = len_a + len_b;
		// 高精度乘法求i的阶乘
		for (j = 0; j < len_a; j++)
		{
			for (k = 0; k < len_b; k++)
			{
				C[j + k] += A[j] * B[k];
				C[j + k + 1] += C[j + k] / 10;
				C[j + k] %= 10;
			}
		}
		while (C[len_c - 1] == 0)
			len_c--;

		// 用高精度加法计算ans
		len_ans = max(len_ans, len_c);
		for (j = 0; j < len_ans; j++)
		{
			ans[i][j] += C[j] + ans[i - 1][j];
			ans[i][j + 1] += ans[i][j] / 10;
			ans[i][j] %= 10;
		}

		// 拷贝数据C给B
        // C:当前阶乘
        // B:上一个数的阶乘
		memcpy(B, C, len_c * sizeof(int));
		len_b = len_c;
	}

	for (int i = 0; i < len_ans; i++)
	{
		cout << ans[n][len_ans - 1 - i];
	}
}