1

我花了一整天的时间来弄清楚如何解决这个问题：[http://www.spoj.com/problems/PARCARD1/]

我从维基百科获得了一些帮助：[http://en.wikipedia.org/wiki/Partition_function_%28number_theory%29#Partition_function]

我终于决定继续这种关系：

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

但是我的实现效率很低...

Python ：

gpn=[1,2,5,7,12,15,22,26,35,40,51,57,70,77,92,100,117,126,145,155,176,187,210,222,247,260,287,301,330,345,376,392,425,442,477,495,532,551,590,610,651,672,715,737,782,805,852,876,925,950,1001,1027,1080,1107,1162,1190,1247,1276,1335,1365,1426,1457,1520,1552,1617,1650,1717,1751,1820,1855,1926,1962,2035,2072,2147,2185,2262,2301,2380,2420,2501,2542,2625,2667,2752,2795,2882,2926,3015,3060,3151,3197,3290,3337,3432,3480,3577,3626,3725,3775,3876,3927,4030,4082,4187,4240,4347,4401,4510,4565,4676,4732,4845,4902,5017,5075,5192,5251,5370,5430,5551,5612,5735,5797,5922,5985,6112,6176,6305,6370,6501,6567,6700,6767,6902,6970,7107,7176,7315,7385,7526,7597,7740,7812,7957,8030,8177,8251,8400,8475,8626,8702,8855,8932,9087,9165,9322,9401,9560,9640,9801,9882,10045]
t=1001
p=[]
for i in range(1001):
        p.append(0)
p[0]=1
i=1
while i<t:
        k=-1
        j=0
        while (gpn[j]<=i):
            if j%2==0:
                k=k*-1
            #print 'k is : %d' % k
            #print p[i-gpn[j]]
            p[i]=p[i]+k*p[i-gpn[j]]
            j+=1
        print p[i],
        i+=1

gpn 是广义五边形数

请帮帮我……我读到可以使用 Hardy-Ramanujan 方法，但它不是近似值，因此在这种情况下会失败……非常感谢。

4

0 回答 0