ZOJ 2865 A very easy task （自然数幂和）

使用递推公式求解。 详见ACdreamer神牛博客：ACdreamer 直接公式法去递推，用大数写了发JAVA

A very easy task

---

Time Limit: 10 Seconds Memory Limit: 32768 KB

---

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

---

Author: SHANG, Zechao Source: ZOJ Monthly, June 2007

import java.io.;
import java.util.;
import java.math.*;

public class Main
{
static BigInteger C[][] = new BigInteger[110][110];

public static void main(String\[\] args) throws IOException
{
    C\[0\]\[0\] = BigInteger.ONE;
    for(int i = 1;i < 110;i++){
        C\[i\]\[0\] = C\[i\]\[i\] = BigInteger.ONE;
        for(int j = 1;j < i;j++)
            C\[i\]\[j\] = C\[i-1\]\[j-1\].add(C\[i-1\]\[j\]);
    }
    Scanner cin = new Scanner(System.in);
    BigInteger n;
    int k;
    BigInteger A\[\] = new BigInteger\[110\];
    while(cin.hasNext()){
        n = cin.nextBigInteger();
        k = cin.nextInt();
        A\[0\] = n;
        for(int i = 1;i <= k;i++){
            A\[i\] = n.add(BigInteger.ONE).pow(i+1);
            A\[i\] = A\[i\].subtract(BigInteger.ONE);
            for(int j = 2;j <= i+1;j++){
                A\[i\] = A\[i\].subtract(C\[i+1\]\[j\].multiply(A\[i+1-j\]));
            }    
            A\[i\] = A\[i\].divide(BigInteger.valueOf(i+1));
        }
        System.out.println(A\[k\]);
    }
}

}