TopCoder SRM 568 Div1 Medium EqualSums

問題

nxnの行列がniceであるということを以下のように定義する。
行列のそれぞれの行に対して、列を重複なく一つずつ選ぶ。
このとき、列をどのように選んだとしても、選んだ成分の和が一定であるときその行列はniceである。

行列が与えられる。
いくつかの成分には0から9の数字が書かれていて、
残りは'-'である。
'-'には0以上の好きな数字を入れてよい。

このとき、この行列をniceにするように'-'に数字を入れる入れ方は何通りあるか、
mod 10^9 + 7で求めよ。

制約条件

n≦50
各行、各列には最低一つ以上'-'でないマスがある。

方針

わからなかったのでeditorialを見た。

i番目の行に対してr[i],
j番目の列に対してc[j]という値を決めて、
a(i, j) = r[i] + c[j]というように行列を作ると、niceな行列が作れ、
なおかつniceな全ての行列に対してそれを作るr, cの決め方が少なくとも一通り存在する。

更に、rの最小値が0になるならば、行列に対してr, cの決め方が一意に定まる。
したがって、rの最小値が0であるようなr, cの決め方の場合の数を求めればよい。

i行目のr[i]をx（x = 0〜9）と決め付ける。
すると、A[i][j]に数字が入っていたら、c[j]がわかる。
というように連鎖的にr, cを埋めていくことができる。
r, cがマイナスにならなければ適切なr, cの決め方だったことがわかる。

同じ行または列に数字があるところは連鎖して辿れるが、
そうでないところは独立なので、場合の数を掛け合わせる必要があるが、
0はどこか一つの行にだけあればよいので、
（全ての連結成分に1つずつある必要はない）その処理が問題になる。

これは、rに0を含まない割り当て方と、全ての割り当て方を両方数えて、
引き算をすればよい。

ソースコード

editorialほぼ写経。

const int mod = (int)1e9 + 7;
vector <string> b;
int n, num[100];
bool v[100];

bool rec(int c){
	v[c] = 1;
	if(c < n){
		rep(i, n) if(b[c][i] != '-'){
			int v = b[c][i] - '0' - num[c];
			if(v < 0) return 0;
			if(num[i + n] < 0){
				num[i + n] = v;
				if(!rec(i + n)) return 0;
			}
			else if(num[i + n] != v) return 0;
		}
	}
	else{
		c -= n;
		rep(i, n) if(b[i][c] != '-'){
			int v = b[i][c] - '0' - num[c + n];
			if(v < 0) return 0;
			if(num[i] < 0){
				num[i] = v;
				if(!rec(i)) return 0;
			}
			else if(num[i] != v) return 0;
		}
	}
	return 1;
}

class EqualSums {
	public:
	int count(vector <string> board) {
		memset(v, 0, sizeof(v));
		b = board;
		n = b.size();
		ll zero = 1, nonzero = 1;
		
		rep(i, n) if(!v[i]){
			v[i] = 1;
			int z = 0, nz = 0;
			rep(j, 10){
				memset(num, -1, sizeof(num));
				num[i] = j;
				if(rec(i)){
					if(std::count(num, num + n, 0)) z++;
					else nz++;
				}
			}
			(zero *= nz + z) %= mod;
			(nonzero *= nz) %= mod;
		}
		return (zero + mod - nonzero) % mod;
	}
};