解题报告：Sum of powers 题目来源：poj No.1707 解法或类型：公式+推导 作者：江云亮 Sum of powers Time Limit:1S Memory Limit:1000K Total Submit:142 Accepted:43 Description A young schoolboy would like to calculate the sum for some fixed natural k and different natural n. He observed that calculating ik for all i (1<=i<=n) and summing up results is a too slow way to do it, because the number of required arithmetical operations increases as n increases. Fortunately, there is another method which takes only a constant number of operations regardless of n. It is possible to show that the sum Sk(n) is equal to some polynomial of degree k+1 in the variable n with rational coefficients, i.e., We require that integer M be positive and as small as possible. Under this condition the entire set of such numbers (i.e. M, ak+1, ak, ... , a1, a0) will be unique for the given k. You have to write a program to find such set of coefficients to help the schoolboy make his calculations quicker. Input The input file contains a single integer k (1<=k<=20). Output Write integer numbers M, ak+1, ak, ... , 1, a0 to the output file in the given order. Numbers should be separated by one space. Remember that you should write the answer with the smallest positive M possible. Sample Input 2 Sample Output 6 2 3 1 0 Source Northeastern Europe 1997 解题思路： 此题应该是比较经典的n次方数的问题。 Pk(n)＝1k＋2k＋…＋nk 我们可以比较迅速的知道如下的公式： K逐渐增大的过程中计算Pk(n)的方法大多采用递推的方法。 如已知P1(n)，P2(n)求P3(n) 因为： 所以： 这样可以通过已知的P1(n)，P2(n)求得P3(n) 这样一层层推导，可以得到更多的Pk(n) 另一种算法可以不利用P1(n)，…，Pk-1(n)就推得Pk(n) 因为当k足够大时递推算法比较麻烦 Bernoulli算法： 可以通过归纳得出Pk(n)的最高次系数为 1／k＋1，进一步归纳可以得到： 因为，所以Bk是Pk(n)的一次项系数，而n＝1时，Pk(1)＝1，所以 由此则逐次可推得（当k＞1而k为奇数时，Bk＝0）。 [证明过程请见：Sum_of_Numbers_Bernoulli算法的证明.doc] 现在我们的问题是找到Bk [Pk(n)的一次项系数],通过套用上述的公式来得到所要求得的Pk(n)，之后再通过对每一项分母的通分来得到题目中要求的m和ak+1, ak, ... , a1, a0 而Bk的值由于题目中的给出计算公式可以计算出： n 分子 分母 1 2 3 -1 1 2 6 0 4 5 6 7 8 9 10 11 12 13 14 15 17 19 -1 30 0 1 42 0 -1 30 0 5 66 0 -691 2730 0 7 6 0 0 0 16 -3617 510 18 43867 798 20 -174611 330 有了这些条件就可以进行计算了。用一个二位数组a[22][2]分别存放系数的分子和分母值。由于涉及到Cmk的运算可能会超出int的范围，其实可以用以下的方法精确无误而且不会越界的算出Cmk。Cmk=k/1*(k-1)/2*(k-3)/3*…*(k-m+1)/m; 求得所有系数中非零项的分母的最小公倍数，即为所求得的m值。而Ak=a[k][0]*m/a[k][1] 这样此题基本得以解决。 时空分析： 使用两个二位数组a[22][2],b[22][2]. 其中a[22][2]存放的是系数的分子和分母。 B[22][2]存放的是伯努力数的分子和分母（分母永远为正） 时间复杂度：O(n^3) 源程序： 1707.cpp 本文来源：https://www.wddqw.com/doc/c24ba8996adc5022aaea998fcc22bcd126ff428b.html