前言
??阶乘之和，一道非常重要的题目，这道题目标志着我们从理论高精度真正转向在实际问题中接入了！
题目概述
AC代码
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 1000
struct Bigint
{
int len, a[maxn];
Bigint(int x = 0)
{
memset(a, 0, sizeof(a));
for (len = 1; x; len++)
a[len] = x % 10, x /= 10;
--len;
}
int &operator[](int i)
{
return a[i];
}
void flatten(int L)
{
len = L;
for (int i = 1; i <= L; ++i)
{
a[i + 1] += a[i] / 10; a[i] %= 10;
}
for (; !a[len];)
len--;
}
void print()
{
for (int i = max(len, 1); i >= 1; --i)
printf("%d", a[i]);
}
};
Bigint operator+(Bigint a, Bigint b)
{
Bigint c;
int len = max(a.len, b.len);
for (int i = 1; i <= len; ++i)
c[i] += a[i] + b[i];
c.flatten(len + 1);
return c;
}
Bigint operator*(Bigint a, int b)
{
Bigint c;
int len = a.len;
for (int i = 1; i <= len; ++i)
c[i] = a[i] * b;
c.flatten(len + 11);
return c;
}
int main()
{
int n;
cin>>n;
Bigint ans(0),fac(1);
for(int i=1;i<=n;++i)
{
fac=fac*i;
ans=ans+fac;
}
ans.print();
return 0;
}
分析思路
1.如果这题数据不是很大的话，其实是一道很简单的题目对吧，阶乘，再求和，这个相信大家都是会做的。然就坏在数据很大上，大到连long long都存不下了，所以我们要接入高精度使用。
2.这里采用了洛谷《深入浅出程序竞赛》的一种写法，众所周知嘛，高精度的题目C++最吃亏，JAVA有大整数类，Python默认无穷大，那么我们可以仿照JAVA，自己实现一个大整数Bigint类。把这个大整数类的模板单独贴一次（注意因为模板里使用了memset函数，所以要引入库文件cstring/string.h ）:
#define maxn 1000
struct Bigint
{
int len, a[maxn];
Bigint(int x = 0)
{
memset(a, 0, sizeof(a));
for (len = 1; x; len++)
a[len] = x % 10, x /= 10;
--len;
}
int &operator[](int i)
{
return a[i];
}
void flatten(int L)
{
len = L;
for (int i = 1; i <= L; ++i)
{
a[i + 1] += a[i] / 10; a[i] %= 10;
}
for (; !a[len];)
len--;
}
void print()
{
for (int i = max(len, 1); i >= 1; --i)
printf("%d", a[i]);
}
};
Bigint operator+(Bigint a, Bigint b)
{
Bigint c;
int len = max(a.len, b.len);
for (int i = 1; i <= len; ++i)
c[i] += a[i] + b[i];
c.flatten(len + 1);
return c;
}
Bigint operator*(Bigint a, int b)
{
Bigint c;
int len = a.len;
for (int i = 1; i <= len; ++i)
c[i] = a[i] * b;
c.flatten(len + 11);
return c;
}
3.注意到这个大整数类给我们提供了很重要的两种算式，高精+高精，以及高精乘低精（我之前说过，乘法更多考的不是高精乘高精）。可以说是非常实用了。然而，如果真的出现其他情况怎么办呢？（比如取余/乘方）等运算？别急，之后的题目会具体介绍
4.引入大整数类后，我们就可以像使用int一样使用Bigint，仅仅在初始化和打印的时候略有区别，那么这道题便不难了。墙裂建议大家都背下这个模板！
文末广告
??学习算法和数据结构真的是个很累的过程，不会做只能求助于题解。 因为写代码这个东西基本上是千人千面。同时网络上搜到的题解很多要么用到的是自己还没学到的知识，看不懂;要么内核过于简陋，只能糊弄当前题目，不具有普适性。
?? 如果你是一个喜欢做洛谷，ACwing和PTA的题目的同学，欢迎关注我的博客，我主要在这三个平台上做题，认为有价值和有难度的题目我会写题解发布出来。
TreeTraverler的往期文章
|