NewOJ 题解 [newoj-1040-阶乘之和] (Python)

题目链接

题目描述

求1!+2!+3!+…+n!,由于答案很大,答案对998244353求余即可。

输入格式

输入存在多组测试数据,对于每组测试数据输入一个正整数n(1<=n<=10^6)

输出格式

对于每组测试数据输出一行表示答案。

输入样例

1
5

输出样例

1
153

思路

这道题,想必大家都知道如何计算,如果在测试数据量比较小的情况下,按照我们原来的方法是没有错的,但是当数据量比较大的情况下,我们原来的那样计算方法,会大大的增加运行时间。解决这道题的核心就是用空间换时间,将之前每次的测试数据的结果都存下来,当下一次再来一条测试数据的时候,如果x小于等于lc我们只需要从数组中取出该条数据即可,如果x大于lc,我们接着第lc次的结果继续运算,并将每次的结果存下来,知道计算出最终结果。

代码实现

import sys
lsu = [1]
ls = [1]
lc = 1
for line in sys.stdin:
    x = eval(line)
    if x <= lc:
        print(lsu[x-1])
    else:
        s = ls[lc-1]
        su = lsu[lc-1]
        for i in range(lc+1,x+1):
            s = (s*i)%998244353
            su = (su+s)%998244353
            ls.append(s)
            lsu.append(su)
            lc += 1
        print(lsu[lc-1])

时间复杂度: O(n)

空间复杂度: O(n)

上一篇:生成实用人名字典


下一篇:springboot启动类启动报Command line is too long