KEYENCE Programming Contest 2019 : D - Double Landscape

最近ほんとAtCoder系のコンテスト調子悪いな。
https://atcoder.jp/contests/keyence2019/tasks/keyence2019_d

問題

N*Mのグリッドの各マスに、1～(N*M)の数字を１つずつ置くことを考える。
各行および各列の最大値が与えられたとき、条件を満たす数字の配置は何通りか答えよ。

解法

各列ないし各行、最大値に相当する値を１個おいてしまえば、残りのマスはそれより小さい数字を任意におけることになる。

数字の大きな順に配置を考えていこう。
数字を置くと、その数字が最大値として設定されている列・行がある場合、その列・行はそれより小さい任意の数字を置けることになる。
列・行それぞれから見ていずれも任意の数字を置けるようになったマスは、以後任意の数字を置ける。
よってそのような任意の数字を置けるマスを適宜数えながらその組み合わせをかけ合わせていこう。

int H,W;
int A[1010],B[1010];
int As[1010*1010];
int Bs[1010*1010];

int C[1010][1010];

ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(As);
	MINUS(Bs);
	cin>>H>>W;
	FOR(i,H) {
		cin>>A[i];
		if(As[A[i]]>=0) return _P("0\n");
		As[A[i]]=i;
	}
	FOR(i,W) {
		cin>>B[i];
		if(Bs[B[i]]>=0) return _P("0\n");
		Bs[B[i]]=i;
	}
	
	ll ret=1;
	int cand=0;
	for(i=H*W;i>=1;i--) {
		if(As[i]>=0 && Bs[i]>=0) {
			FOR(x,W) {
				if(C[As[i]][x]==1) cand++;
				C[As[i]][x]++;
			}
			FOR(y,H) {
				if(C[y][Bs[i]]==1) cand++;
				C[y][Bs[i]]++;
			}
			
		}
		else if(As[i]>=0) {
			int pat=0;
			FOR(x,W) {
				if(C[As[i]][x]==1) cand++;
				C[As[i]][x]++;
				if(C[As[i]][x]==2) pat++;
			}
			ret=ret*pat%mo;
		}
		else if(Bs[i]>=0) {
			int pat=0;
			FOR(y,H) {
				if(C[y][Bs[i]]==1) cand++;
				C[y][Bs[i]]++;
				if(C[y][Bs[i]]==2) pat++;
			}
			ret=ret*pat%mo;
		}
		else {
			ret=ret*cand%mo;
		}
		cand--;
		
	}
	
	cout<<ret<<endl;
}

まとめ

ここまではまぁ問題なかったんだが。