editorial : http://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A
A magic matrix is a square matrix filled with digits (0-9) such that its row sums and column sums
all have the same last digit.
John has n by n matrix. some of them are filled and the others are empty.
Find the number of ways to get a magic matrix assigning values to the empty cells.
n > 10 だと空の列,行があるので,簡単.
n <= 10 の場合は,連立方程式 (Ax = b) の解の個数になる.
modulo が素数ならば,体なので,自由に割り当てられる変数の個数は,変数の数 - (行列 A のランク) になる.
modulo が素数でないので Chinese remainder theorem を使う.
ただ単に,mod 2 での解の個数と,mod 5 での解の個数を掛けあわせれば良い.
何故なら,Ax = b (mod 2), Ay = b (mod 5) を満たす x, y のペアと, Az = b (mod 10) を満たす z の間には一対一の対応があるから.