poj 2094 多项式求和。

 1 /**
 2 给出多项式 p(x) = an*x^n + an-1*x^(n-1)..... + a1*x + a0;
 3 给定n，l，k，m 计算 x 从 l到 l+k-1 的p（x）的后m 位的平方的和
 4 
 5 用差分序列 ，先计算出前 n项 构造出差分表。。后边的k-n个  用递推可得，从下往上递推。
 6 **/
 7 
 8 import java.math.BigInteger;
 9 import java.util.Scanner;
10 
11 public class Main {
12 
13         public static int cal(String str, int m) {
14                // System.out.println(str+"------->");
15                int len = Math.min(str.length(), m);
16                int ans = 0, tmp;
17                for (int i = 0; i < len; i++) {
18                      tmp = str.charAt(i) - '0';
19                      ans += tmp * tmp;
20               }
21                return ans;
22        }
23 
24         public static void main(String[] args) {
25               Scanner cin = new Scanner(System. in);
26                int n = cin.nextInt();
27               BigInteger l = cin.nextBigInteger();
28                int k = cin.nextInt();
29                int m = cin.nextInt();
30               BigInteger mod = BigInteger. TEN.pow(m);
31               BigInteger[] a = new BigInteger[15];
32                for (int i = 0; i <= n; i++)
33                      a[i] = cin.nextBigInteger();
34               BigInteger h[][] = new BigInteger[15][15];
35                for (int i = 0; i < Math.min (n + 1, k); i++) {
36                      BigInteger res = a[0];
37                       for (int j = 1; j <= n; j++) {
38                            res = res.multiply(l);
39                            res = res.add(a[j]);
40                      }
41                      res = res.mod(mod);
42                      l = l.add(BigInteger. ONE);
43                      h[0][i] = res;
44                      System. out.println(cal(res.toString(), m));
45               }
46 
47                if (k > n + 1) {
48                       for (int i = 1; i <= n; i++) {
49                             for (int j = 0; j <= n - i; j++)
50                                   h[i][j] = h[i - 1][j + 1].subtract(h[i - 1][j]);
51                      }
52               }
53 
54               BigInteger pre[] = new BigInteger[15];
55                for (int i = 0; i <= n; i++) {
56                      pre[i] = h[i][n - i];
57               }
58                for (int i = n + 1; i < k; i++) {
59                      BigInteger res = h[n][0];
60                       for (int j = n - 1; j >= 0; j--) {
61                            res = pre[j].add(res);
62                            res = res.mod(mod);
63                            pre[j] = res;
64                      }
65                      System. out.println(cal(res.toString(), m));
66               }
67        }
68 
69 }