2013
11-10

# 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.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);
}
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);
}