[DP] 整数分解

题目描述见<a href="http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1255">这里</a>。
Q(i,j) - 数i的分解方式中以j起始的分解总数.显然,1<=j<=i.
Q(i,j) - 值如下图:
![](http://www.forkosh.com/mathtex.cgi? Q(i,j) = \sum_{k=j}^{i-j}Q(i-j,k))

那么, 数i的所有分解方式 应该为
![](http://www.forkosh.com/mathtex.cgi? \sum_{j=1}^{i}Q(i,j))
其中,所有满足i/2<=j<iQ(i,j),值为0。

另外,本题需要在模P意义下求解,用到了数论里模运算的法则:

 ( a mod p + c mod p ) mod p == ( a + c ) mod p

另外的另外,本题是多个case输入,每次都去计算一遍Q的array会TLE。这里的以空间换时间策略还是对编程能力比较有提高的.

(fuck - 后面浪费我好多时间)

可是如果一次性计算出400×400的array之和会令long long溢出,溢出的时候就要老老实实地再去加一遍了(事先存下every line's sum of 400×400 array, 每次只需要计算前k个累积和即可)。(这里用unsigned long long没有试过).

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容