AtCoder Beginner Contest 003 D - AtCoder社の冬
解法
ちょっとアホな方法で通してしまったんですが, 後で紹介します。
まず前提として, この問題は結局「X*Y の長方形を作るように D+L 個の物体を配置する方法は何通りあるのか」というのが求められれば, あとはそれに comb[D+L][D] * (R-X+1) * (C-Y+1) をかけるだけで問題が解けます。
想定解は多分包除原理です。
例えば「X*Y の長方形の上の辺に絶対頂点が存在しない場合」などを考えて, 「X*Y の長方形の好きなところに頂点を並べた場合」から引くことを考えます。ただ, これだと「X*Y の長方形の上と下の辺に絶対頂点が存在しない場合」などを考えてないので数え漏れがあります。こういうのを包除原理でカバーすれば良いだけです。
const ll MOD = 1e9+7; const int MAX = 1000; ll comb[2*MAX][2*MAX]; int main() { cin.tie(0); ios::sync_with_stdio(false); for (int i = 0; i < 2*MAX; i++) { comb[i][0] = 1; for (int j = 1; j <= i; j++) { comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD; } } int R, C, X, Y, D, L; cin >> R >> C >> X >> Y >> D >> L; ll ans = 0; for (int s = 0; s < 1<<4; s++) { int h = X, w = Y; if (s&1) h--; if (s&2) h--; if (s&4) w--; if (s&8) w--; if (h < 0 || w < 0) continue; ll tmp = comb[h*w][L+D]; if (__builtin_popcount(s)%2) tmp = MOD-tmp; ans += tmp; } ans %= MOD; (ans *= comb[D+L][L]) %= MOD; (ans *= (R-X+1)*(C-Y+1)) %= MOD; cout << ans << endl; return 0; }
自分のやった方法は, 上の辺, 下の辺, 右の辺, 左の辺に来る頂点数及び「左上などのかどっこに頂点はあるか」で場合分けして, それぞれの場合の数を求める, ということをやりました。計算量結構ギリギリ。
const ll MOD = 1e9+7; const int MAX = 1000; ll comb[2*MAX][2*MAX]; ll calc(int total, int contain, int left, int right) { if (left == 1 && right == 1) return comb[total-2][contain-2]; else if (left == 1 || right == 1) return comb[total-2][contain-1]; else return comb[total-2][contain]; } int main() { cin.tie(0); ios::sync_with_stdio(false); for (int i = 0; i < 2*MAX; i++) { comb[i][0] = 1; for (int j = 1; j <= i; j++) { comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD; } } int R, C, X, Y, D, L; cin >> R >> C >> X >> Y >> D >> L; if (X*Y < D+L) { cout << 0 << endl; return 0; } ll ans = 0; if (X==1 && Y==1) ans = 1; else if (X==1 || Y==1) { int Z = max(X, Y); if (D+L <= 1) ans = 0; else { ans = comb[Z-2][D+L-2]; } } else { ans = 0; int inner = X*Y - (2*X+2*Y) + 4; for (int u = 1; u <= Y; u++) for (int d = 1; d <= Y; d++) { for (int l = 1; l <= X; l++) for (int r = 1; r <= X; r++) { for (int flag = 0; flag < 1<<4; flag++) { int rest = D+L-u-l-d-r; ll tmp = 1; int ul = !!(flag&1); int ur = !!(flag&2); int dl = !!(flag&4); int dr = !!(flag&8); if (ul) rest++; if (ur) rest++; if (dl) rest++; if (dr) rest++; if (rest < 0) continue; (tmp *= comb[inner][rest]) %= MOD; (tmp *= calc(Y, u, ul, ur)) %= MOD; (tmp *= calc(Y, d, dl, dr)) %= MOD; (tmp *= calc(X, l, ul, dl)) %= MOD; (tmp *= calc(X, r, dr, ur)) %= MOD; (ans += tmp) %= MOD; } } } } (ans *= comb[D+L][D]) %= MOD; (ans *= (R-X+1)*(C-Y+1)) %= MOD; cout << ans << endl; return 0; }