pe-0078

整数划分:把一个整数表示成若干别的数字的加和形式.

使用dp可以让复杂度压成 $n^2$ ,还不够.

上网查阅结论得知,划分数 $p(n)$ 有以下性质:

$$p(k)=p(k-1)+p(k-2)-p(k-5)-p(k-7)+p(k-12)+p(k-15)-p(k-22)-++--...$$

其中p(0)认为是1,负的认为是0.

其中这个减掉的数列叫做 五边形数 ,满足通项公式(注意这个通项是正负交替的, $0,1,-1,2,-2,…$ )

$$a_n=n(3n-1)/2,n\in\{0,\pm1,\pm2,\pm3,...\}$$

然后求能被1000000整除的那一项就可以计算了,注意对1000000取模就不会炸int.