TopCoder SRM 644 Div1 Hard SquareOfSquareMatrix

近いところまでは考えられたけど、自力回答ならず。

問題

N次正方行列がある。
この行列の各要素は0か1のみで構成されている。
このうちM個の要素は1が入ることが確定している。

この行列を２乗したとき、ゼロ行列となるような元行列は何通りあるか答えよ。

解法

他の解答を見る限り、色々な解法があるようだ。
ここでは自分が参考にした軽めのO(N^3)解法を紹介。

r行目c列目が1となる場合、２乗してゼロ行列であるためにはc行目各要素とr列目各要素は0でなければならない。
まずそのように0でなければならない行・列を列挙する。

各xを以下の４つに分類する。

1. x行目もx列目それぞれ1であっても良い。：L個
2. x行目は0でなければならない＝x列目に1が含まれる。：R個
3. x列目は0でなければならない＝x行目に1が含まれる。：C個
4. x列目もx行目も0でなければならない→このケースはすでに２乗して非0成分が含まれてしまうので、解が0個で終了。

この状態は、C行R列の計C*R個中M個1が入っていることになる。
残り(C*R-M)個の要素は0でも1でも２乗して非ゼロ行列を生成することはないので、2^(C*R-M)通り考えることができる。

L個の行・列から

• 1が含まれる列の数がR'個
• 1が含まれる行の数がC'個

を追加することを考える。
前提として、R'+C'≦Lでなければならない。そうでないと２乗して非0成分が生じてしまう。

L個の行・列からR'個の列、C'個の列を選択するのは、全体で通りである。
ただしこれは0だけで構成される列・行を含んでいる可能性があるので、包除原理の容量でそれらを減算していけば良い。

ll mo=1000000007;
int R[501],C[501];

const int CN=601;
ll CC[CN][CN];
ll dp[CN][CN];

class SquareOfSquareMatrix {
	public:
	int count(int n, vector <int> r, vector <int> c) {
		int i,j,y,x;
		
		vector<ll> p2;
		p2.push_back(1);
		FOR(i,502*502) p2.push_back(p2.back()*2%mo);
		FOR(i,CN) for(j=0;j<=i;j++) CC[i][j]=(j==0||j==i)?1:(CC[i-1][j-1]+CC[i-1][j])%mo;
		
		ZERO(R);
		ZERO(C);
		FOR(i,r.size()) r[i]--,c[i]--, C[r[i]]=R[c[i]]=1;
		
		int ro=0,co=0;
		FOR(x,n) {
			if(R[x]&&C[x]) return 0;
			if(R[x]) ro++;
			if(C[x]) co++;
		}
		int left=n-ro-co,rn,cn;
		FOR(i,501) FOR(j,501-i) dp[i][j]=p2[(i+ro)*(j+co)-r.size()];
		for(i=0;i<=501;i++) for(j=0;j<=501-i;j++) for(x=0;x<j;x++) (dp[i][j]-=dp[i][x]*CC[j][x]%mo)%=mo;
		for(i=0;i<=501;i++) for(j=0;j<=501-i;j++) for(x=0;x<j;x++) (dp[j][i]-=dp[x][i]*CC[j][x]%mo)%=mo;
		FOR(i,501) FOR(j,501-i) ((dp[i][j]%=mo)+=mo)%=mo;
		
		ll ret=0;
		FOR(rn,left+1) FOR(cn,left+1-rn) (ret+=dp[rn][cn] * CC[left][rn] % mo * CC[left-rn][cn] % mo)%=mo;
		return (int)ret;
	}
}

まとめ

O(N^2)っぽい解法の人もいたけど、解法がよく理解できなかった。