PKU3420 - Quad Tiling

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3420

Typical DP problem when N is small.

In this problem, N can be as large as 10^9, so matrix multiplication should be used. Unlike the problem I've done before, this time the matrix is as large as 16x16 (because there is 2^4 number of states at each layer). I write code to pre-generate the 16x16 matrix instead of hard-coding the formula, and then do matrix multiplication as usual.

PKU3471 - Integral Roots

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3471

The problem is given an integral coefficient polynomial, find all integral roots of it.

If there is repeated root, output them repeatedly.

For the integral roots of the polynomial, it must be a factor of the constant term of the polynomial. We then can factorized the constant term and verify the factors to the polynomial one by one.

However, overflow will occur during the verification (the degree of the polynomial may be as large as 100), how should we verify the solution safely?

One method is that you can calculate the polynomial by repeatedly dividing and subtracting each terms. For example, ax^2 + bx + c = 0, it can be rewritten as ax + b = -c/x. As the LHS of the equation is integer, the c/x must be integer. Using this method, we can avoid overflow in our calculation.

This has not solved the problem. We have not identified the repeated roots. One way to find the multiplicity of roots is to check f(x), f'(x), f''(x), and so on, and they should all be zero. But calculating the derivatives of f may again lead to overflow.

The method I finally used is to do polynomial division.

I repeatedly divide the polynomial by (x - c). If that is divisible, then c is a root of it, and use the quotient to continue the process. This can avoid all overflow problems, and find the repeated roots successfully.

Be careful on the cases that zero is the root of the polynomial.