脚本宝典收集整理的这篇文章主要介绍了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])

@R_394_1304@: O(n)

空间复杂度: O(n)

脚本宝典总结

以上是脚本宝典为你收集整理的NewOJ 题解 [newoj-1040-阶乘之和] (Python)全部内容，希望文章能够帮你解决NewOJ 题解 [newoj-1040-阶乘之和] (Python)所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。