Codeforces #277.5 Div2 F. Special Matrices

Eより簡単。
http://codeforces.com/contest/489/problem/F

問題

N*Nの行列がある。
この時、どの列も２つだけ1となる要素があり、どの行も２つだけ1となる要素があり、それ以外の要素は0であるような行列は特別な行列とする。

N*N行列のうち、上M行分、M*N要素が与えられる。
残りの(N-M)行を埋めて構築できる特別な行列は何通りあるか。

解法

まず各列において1の登場数を求め、残り(N-M)行に何個1が登場しなければならないか求める。
するとあと２個登場しないといけない列の数と、１個登場しないといけない列の数がわかる。

２個登場しないといけない列がN個、１個登場しないといけない列がM個ある場合、次の行の選択のしかたは以下の３通りとなる。

• N個から２列選ぶのが通り。
• M個から２列選ぶのが通り。
• N個とM個から１列ずつ選ぶのがN*M通り。

後は単純なメモ化再帰で解ける。

int N,M;
ll mo;
string S[501],SS;
int n1=0,n2=0;
ll dp[1201][1201];
int num[501];

ll dpdp(int N2,int N1) {
	if(N2+N1==1) return 0;
	if(N2+N1==0) return 1;
	if(dp[N2][N1]>=0) return dp[N2][N1];
	dp[N2][N1]=0;
	if(N2>=2) dp[N2][N1] += N2*(N2-1)/2*dpdp(N2-2,N1+2)%mo;
	if(N1>=2) dp[N2][N1] += N1*(N1-1)/2*dpdp(N2,N1-2)%mo;
	if(N2>=1 && N1>=1) dp[N2][N1] += N2*N1*dpdp(N2-1,N1)%mo;
	return dp[N2][N1]%=mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>mo;
	
	FOR(x,N) SS+='2';
	FOR(y,M) {
		cin>>S[y];
		if(count(S[y].begin(),S[y].end(),'1')!=2) return _P("0\n");
		FOR(x,N) num[x]+=S[y][x]=='1';
	}
	FOR(x,N) n1+=num[x]==1,n2+=num[x]==0;
	MINUS(dp);
	cout << dpdp(n2,n1) <<endl;
	
}

まとめ

割と典型な気がする。