http://acm.pku.edu.cn/JudgeOnline/problem?id=3742
高精度加法和乘法.
复杂度: O(aN
2)(a为高精度的代价)
/**
* @version 2009/08/28
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
private static final int MAX_N = 200;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static BigInteger[][] C = new BigInteger[MAX_N + 1][];
private static BigInteger[] a = new BigInteger[MAX_N + 1];
private static BigInteger[] pow = new BigInteger[MAX_N + 1];
public static void main(String[] argv) throws Exception {
int N, t, signalt, signal;
int i, j;
BigInteger T, x;
initialize();
while (in.ready()) {
N = nextInt();
t = nextInt();
if (t < 0) {
t = -t;
signalt = 1;
} else signalt = -1;
T = BigInteger.valueOf(t);
pow[0] = BigInteger.ONE;
for (i = 1; i <= N; i++) pow[i] = pow[i - 1].multiply(T);
for (i = 0; i <= N; i++)
a[i] = BigInteger.valueOf(nextInt());
for (i = N; i >= 0; i--) {
for (signal = signalt, j = i - 1; j >= 0; j--, signal *= signalt) {
x = a[i].multiply(C[i][j]).multiply(pow[i - j]);
if (signal < 0) a[j] = a[j].subtract(x.negate());
else a[j] = a[j].subtract(x);
}
}
for (i = 0; i <= N; i++) {
if (i != 0) System.out.print(" ");
System.out.print(a[i]);
}
System.out.println();
}
}
private static void initialize() {
int i, j;
C[0] = new BigInteger[1];
C[0][0] = BigInteger.ONE;
for (i = 1; i <= MAX_N; i++) {
C[i] = new BigInteger[i + 1];
C[i][0] = C[i][i] = BigInteger.ONE;
for (j = 1; j < i; j++)
C[i][j] = C[i - 1][j - 1].add(C[i - 1][j]);
}
}
private static int nextInt() throws Exception {
return Integer.parseInt(next());
}
private static String next() throws Exception {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(in.readLine());
return st.nextToken();
}
}