Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2014-06-07

TCO 2013 2A 500

21:27

editorial : http://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A

Problem

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.

制約
  • すでに埋まっているセルは10個以下
  • n <= 1000

解法

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 の間には一対一の対応があるから.

 |