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\]);
    }
}

}

------ 本文结束------
  • 本文作者: kuangbin
  • 本文链接: 447.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
0%