题目描述见<a href="http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1255">这里</a>。
Q(i,j) - 数i的分解方式中以j起始的分解总数.显然,1<=j<=i.
Q(i,j) - 值如下图:
 = \sum_{k=j}^{i-j}Q(i-j,k))
那么, 数i的所有分解方式 应该为
)
其中,所有满足i/2<=j<i的Q(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没有试过).