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 }
poj 2094 多项式求和。,布布扣,bubuko.com
原文:http://www.cnblogs.com/Bang-cansee/p/3724084.html