首页 > 专题系列 > Java解POJ > POJ 2515 Birthday Cake [解题报告] Java
2013
11-11

POJ 2515 Birthday Cake [解题报告] Java

Birthday Cake

问题描述 :

Prince Remmarguts helped Uyuw successfully hold a concert in our previous story (POJ 2451), and …that was the day of Uyuw’s birthday.

Ting-a-ling, the chef was called on by Remmarguts. “You must prepare an immense birthday cake for lovely Princess Uyuw in a single day,” said Remmarguts. Though Remmarguts’ order is outrageous, the chef eventually rushed to buy flour, sugar, fat, and some other ingredients.

There had been chaos caused by war for quite a long time. The price of everything has been highly raised. Being the head accountant of country UDF – United Delta of Freedom, you must weight the cake carefully to make sure the chef did not perform a cheat on the ingredients.

The cake is made up of N levels. There is a ‘cube’ in each level, while the length of cube on k-th level (count from the topmost) is exactly k! For Remmarguts lives in an M-Dimension world unlike our, you should notice that the ‘cube’ here means M-Dimension cube, and the volume of a cube with length k is k ^ M.

You are to calculate the total volume of such an immense cake.

输入:

You should read the number of test cases Z (Z <= 30) in the first line. Each of the following lines denotes a single test case, consisting of two integers N and M. We guarantee that 1 <= N <= 10 ^ 41 and 3 <= M <= 100.

输出:

Output one line per test case, showing the total volume of that cake. We also guarantee that the volume is less than 10 ^ 250.

样例输入:

2
3 3
6 5

样例输出:

36
12201

解题代码:

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

/**
 *
 * @author gongshaoqing
 */
public class Main {
private static  int  NULL=0;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int i, j, t;
        int m;
        BigInteger N, b[][], c,ans,temp;
        b = new BigInteger[102][102];
        b[1][1]=BigInteger.ONE;
        b[2][1]=BigInteger.ONE;
        b[2][2]=BigInteger.valueOf(2);
        for (i = 3; i <= 100; i++) {
            b[i][1]=BigInteger.ONE;
            for (j = 2; j <= i; j++) {
                if((i-1)< j)b[i-1][j]=BigInteger.ZERO;
                b[i][j]=b[i-1][j-1].add(b[i-1][j]);
                b[i][j]=b[i][j].multiply(BigInteger.valueOf(j));

            }
        }
        /*for(i=1;i<=100;i++)
        {   for(j=1;j<=i;j++)
                System.out.print(b[i][j]+" ");
            System.out.println();
        }*/
        t=cin.nextInt();
        while(cin.hasNext())
        {
            if(t==0)break;
            t--;
            N=cin.nextBigInteger();
            m=cin.nextInt();
            temp=N.add(BigInteger.ONE);

            ans=BigInteger.ZERO;
            for(i=1;i<=m;i++)
            {
                c=temp.multiply(N);
                temp=c.divide(BigInteger.valueOf(i+1));
                c=temp.multiply(b[m][i]);
                ans=ans.add(c);
                N=N.subtract(BigInteger.ONE);
                if(N.compareTo(BigInteger.ZERO)==0) break;
            }
            System.out.println(ans);
        }
        // TODO code application logic here
    }
}

  1. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。