问个题目，求个高效的算法
This task is very simple.
You are to calculate ∑ik (1 <= i <= n).
Input:
There are multiple cases in the input.
Each case begins with two integer n and k (0 <= n <= 1050, 1 <= k <= 100).
Output:
For each test, print the answer in a single line.
Sample Input:
2 3
3 2
Sample Output:
9
14
题目链接： http://acm.zju.edu.cn/show_problem.php?pid=2865
看到最好的解决情况：
Rank Submit-time Run-time Run-memory Language User
1 2007-06-1613:27:56 00:00:05 888K C++ xxoo
[解决办法]
对于这个问题，我不知道有没有公式，好像听说有，又好像记得华罗庚在《数论导引》里用函数逼近给出了该结果k+1次多项式的系数.
在《初等述论III》里找到一种解法：
前n个自然数的方幂和问题。
首先推导二次幂和公式，
(n+1)^3 - n^3 = 3*n^2 + 3*n + 1
n^3 - (n-1)^3 = 3*(n-1)^2 + 3*(n-1) + 1
... ...
2^3 - 1^3 = 3*(1)^3 + 3*(1) + 1
两边相加，(n+1)^3 - 1^3 = 3*∑i^2 + 3*∑i + n; (∑的求和指标为1 <=i <=n，下同)
得，∑i^2 = (1/6)*n*(n+1)*(2*n+1)
同理可推导得
三次幂的和的公式，(n+1)^4 - 1 = 4*∑i^3 + 6*∑i^2 + 4*∑i + n
四次幂的和的公式，(n+1)^5 - 1 = 5*∑i^4 + 10*∑i^3 + 10*∑i^2 + 5*∑i + n
五次幂的和的公式，(n+1)^6 - 1 = 6*∑i^5 + 15*∑i^4 + 20*∑i^3 + 15*∑i^2 + 6*∑i + n
... ...
不难发现，这里∑前面的系数是二项式系数，c(j, p), 1 <=j <=p;
(n+1)^p - 1 = ∑( c(j,p)*∑i^(p-j) ),内层∑求和指标为1 <=i <=n，外层∑求和指标为1 <=j <=p
从编程角度讲，为求∑i^k,只令p=k+1，题目中1 <=k <=100，保存前∑i^1到∑i^(k-1)没问题.
max{(n+1)^p} > 10^5051,弄个大数，看看能不能过。
[解决办法]
wxspll(HDU) 我和你的思路是一样的.
写完代码后才发现问题.
首先,要把C(n,k)保存下来,否则多次计算时间不够.
如果把C(100,k)都保存下来的话,需要100个大整数, 然后还有吧∑i^(p) 0 <p <k也保存下来.也需要100个大整数.
然后算上中间结果的保存,算下来差不多要1M的内存,我的大整数是放在栈里的,结果栈溢出啦.
[解决办法]
是这个题目呀。
可以记
C(k,n)=n*(n-1)*(n-2)*...*(n-k+1)
那么
n=C(1,n)
n^2=C(2,n)+C(1,n)
n^3=C(3,n)+3C(2,n)+C(1,n)
n^4=C(4,n)+6C(3,n)+7C(2,n)+C(1,n)
而
n*C(k,n)=C(k+1,n)+k C(k,n)
我们通过这个递推式可以非常容易的计算出
n^k表示成C(k,n), C(k-1,n),...,C(1,n)的和中各项的系数。
然后
由于
C(k,n)=[C(k+1,n+1)-C(k+1,n)]/(k+1)
可以得到
C(k,n)+C(k,n-1)+...+C(1,k)=[C(k+1,n+1)-C(k+1,1)]/(k+1)
我们可以非常容易的得到最终结果
[解决办法]
这个涉及到了伯努利数。
自然数k次方和有如下公式：
n-1 1 n
∑ i^k=-----∑(k+1,i)*B(i)*n^(k+1-i) (1)
i=0 k+1 i=0
式中，(k+1,i)表示k+1个选i个的组合数；B(i)成为第i个伯努利数。
由式(1)知：如果预先存好(k+1,i)的值，而且知道如何计算出B(i)，那么，问题完全有可能在极短的时间内得解。
(k+1,i)的值是易于计算的。
关于伯努利数的计算，一般地：
n> =1时,有B(2n+1)=0;
n> =2时,有公式B(n)=∑[C(k,n)*B(k)](k:0-> n)
初值条件为B0 = 1。
以下列出前几个伯努利数：
B(0)=1,B(1)=-1/2,
B(2)=1/6,B(3)=0,
B(4)=-1/30,B(5)=0,
B(6)=1/42,B(7)=0,
B(8)=-1/30,B(9)=0),
B(10)=5/66,B(11)=0,
B(12)=-691/2730,B(13)=0,
B(14)=7/6,B(15)=0,
B(16)=-3617/510,B(17)=0,
B(18)=43867/798,B(18)=0,
有了这些，问题已经十分简单了。
