首页 > 专题系列 > Java解POJ > POJ 2094 Angry Teacher [解题报告] Java
2013
11-10

POJ 2094 Angry Teacher [解题报告] Java

Angry Teacher

问题描述 :

Mr. O’Cruel is teaching Math to ninth grade students. Students of course are very lazy, so they do not like to do their homework. On the other side, Mr. O’Cruel doesn’t like lazy students.

Recently Andrew failed to do his homework again, so he was given a special task. If he doesn’t do it, he will be expelled from his school. The task seems very easy, but it is very technical, so it would take a lot of time. Andrew is given a polynomial p(x) = anxn + an-1xn-1 + . . . + a1x + a0 with integer coefficients.

He must calculate the value of the polynomial for k successive integer numbers starting from l. Of course writing all these numbers would require too much paper. So as a proof of completing the task, for each number x from l to l + k – 1 Andrew is asked to provide the sum of squares of m last digits in decimal notation of p(x).

Since Andrew is lazy, he doesn’t want to do the task by himself. So he asks you to write the program that calculates the values requested.

输入:

The first line of the input file contains n, l, k, and m (0 <= n <= 10, 0 <= l <= 101000 , 1 <= k <= 1 000, 1 <= m <= 1 000).

The following n + 1 lines contain coefficients of the polynomial: an , an-1 , . . . , a1 , a0 (0 <= ai <= 101000).

输出:

Output k lines — for x from l to l + k – 1 output the sum of squares of last m digits of p(x).

样例输入:

3 0 10 2
1
0
2
1

样例输出:

1
16
10
25
58
45
85
89
85
80

解题代码:

//* @author: 
import java.math.*;
import java.util.*;

public class Main {
 static BigInteger l, t;
 static int m, n, k;
 static BigInteger[] a = new BigInteger[15];
 static BigInteger[][] q = new BigInteger[15][15];
 static char[] c;
 static char[] cc;

 public static void main(String[] args) {
   Scanner in = new Scanner(System.in);
   n = in.nextInt();
   l = new BigInteger(in.next());
   k = in.nextInt();
   m = in.nextInt();
   BigInteger w = BigInteger.TEN.pow(m);
   for (int i = 0; i <= n; ++i)
	a[i] = new BigInteger(in.next());
 	for (int i = 0; i < Math.min(k, n + 1); ++i) {
        t = a[0];
	 for (int j = 1; j <= n; ++j) {
	   t = t.multiply(l);
	   t = t.add(a[j]);
	  }
	 t=t.mod(w);
	 q[n][i] = t.mod(w);
	 int ret = 0;
	 c = t.toString().toCharArray();
	 int ll = c.length;
	 for (int j = 0; j < Math.min(m, ll); ++j) {
	  ret += (c[ll - 1 - j] - '0') * (c[ll - 1 - j] - '0');
	 }
	 System.out.println(ret);
	 l = l.add(BigInteger.ONE);
	}
	if (k > n) {
	  for (int i = n - 1; i >= 0; --i) {
	   for (int j = 0; j <= i; j++)
	    q[i][j] = q[i + 1][j + 1].subtract(q[i + 1][j]).mod(w);
	   }
	  for(int i=1;i<=n;++i)
	   q[0][i]=q[0][0];
	   int po = 1;
	   for (int i = n + 1; i < k; ++i) {
	    for (int j = 1; j <= n; ++j)
		q[j][(po + j) % (n + 1)] = q[j - 1][(po + j - 1) % (n + 1)]
		 .add(q[j][(po + j - 1) % (n + 1)]).mod(w);
		int ret = 0;
		c = q[n][(po + n) % (n + 1)].mod(w).toString().toCharArray();
		int ll = c.length;
		for (int j = 0; j < Math.min(m, ll); ++j) {
		  ret += (c[ll - 1 - j] - '0') * (c[ll - 1 - j] - '0');
		}
		System.out.println(ret);
		l = l.add(BigInteger.ONE);
		++po;
	    }
	 }
	}
}

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

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.