TopCoderOpen 2013 Round2A Medium TheMagicMatrix

これも長らく解いていなかったのでトライ。
http://community.topcoder.com/stat?c=problem_statement&pm=12495

問題

N×Nの正方行列の各要素に0～9の数字を埋めることを考える。
このうちM個は数字が指定される。

行列の各列および各行の和の1の位が同じになるように行列の数字を埋める場合、その組み合わせ数を答えよ。

問題

1つも要素が指定されない行および列が1つ以上あれば、他の行および列の要素が何であっても、その行・列で1の位が等しくなるよう調整できるので、答えは通り。

あとは全部の列・行に1つ以上要素がある場合を考えればよい。
指定される数字は最大で10箇所なので、以後はN<=10となる。

行列をA、和の1の位をXとすると、各j行についてかつ各i列についてを満たすAを求めればよい。

ただ、このままだとXが0～9と10通りあって扱いにくいので、X自体も変数として左辺に持ってくると、以下のN^2+1変数からなる2N+M個の式を立てることができる。

• 各行の和の1の位が一致：
• 各列の和の1の位が一致：
• 数値Vが指定された要素について、

上記の式はそのままだとmod10で扱いにくいが、mod 2とmod 5でそれぞれ上記式を満たせば mod 10でも満たすことになるので、それぞれの組み合わせ数は方程式のrank Rから、mod 2・5それぞれなら、を掛け合わせればよい。
rankはガウスの掃出し法で求める。

rankやガウスの掃出し法はちょうどSRM590 D1M XorCardsでやったね。

ll mo=1234567891;
int nn;
// a^n % p
ll modpow(ll a, ll n, ll p) {
	ll r=1;
	while(n) {
		if(n%2) r=(r*a)%p;
		a=(a*a)%p;
		n>>=1;
	}
	return r;
}

int a[200][200],r[200];
ll pat(int mod) {
	int i,j,x,y;
	int A[200][200],R[200];
	int rev[5];
	
	rev[0]=0; rev[1]=1;
	if(mod==5) rev[2]=3,rev[3]=2,rev[4]=4;
	FOR(i,200) {
		R[i]=((r[i]%mod)+mod) % mod;
		FOR(j,200) A[i][j]=((a[i][j]%mod)+mod) % mod;
	}
	int po=0;
	FOR(i,200) {
		for(j=po;j<200;j++) if(A[j][i]) break;
		if(j==200) continue;
		
		FOR(x,200) swap(A[j][x],A[po][x]);
		swap(R[j],R[po]);
		
		j=rev[A[po][i]];
		FOR(x,200) A[po][x]=(A[po][x]*j)%mod;
		R[po]=(R[po]*j)%mod;
		
		for(x=po+1;x<200;x++) if(A[x][i]) {
			int tot=0;
			R[x] = (((R[x] - R[po]*A[x][i])%mod)+mod) % mod;
			for(j=199;j>=i;j--) tot += (A[x][j] = (((A[x][j] - A[po][j]*A[x][i])%mod)+mod) % mod);
			if(tot==0 && R[x]) return 0;
		}
		
		po++;
	}
	
	return modpow(mod,nn*nn+1-po,mo);
}


class TheMagicMatrix {
	public:
	int find(int n, vector <int> rows, vector <int> columns, vector <int> values) {
		int i,x,y;
		nn=n;
		int N=rows.size();
		if(n>N) return modpow(10,(n-1)*(n-1)-N+1,mo);
		
		ZERO(a);
		ZERO(r);
		// row
		FOR(y,n) {
			FOR(x,n) a[y][y*10+x] = 1;
			a[y][100]=-1;
		}
		// col 
		FOR(y,n) {
			FOR(x,n) a[n+y][x*10+y] = 1;
			a[n+y][100]=-1;
		}
		
		FOR(i,N) {
			a[2*n+i][rows[i]*10+columns[i]] = 1;
			r[2*n+i] = values[i];
		}
		
		return (int)(pat(2)*pat(5)%mo);
	}

};

まとめ

XorCardsとこの問題で、だいぶrankを使った方程式の解の数と、連立方程式の解き方に慣れた気がする。