SRM 573 div2 hard: WolfPackDivTwo

まだ見てないけど div1 hard がこれの強化版らしく震えている。

問題

TopCoder Statistics - Problem Statement

解法

集まる可能性のある場所が, [-50, 100] * [-50, 100] ぐらいしか無いので, それぞれの集合場所でそれぞれの牛が集合場所に何通りの場合ですすめるかを考えれば良いです。

牛が m 回の移動で (dx, dy) (dx >= 0, dy >= 0 としておく)だけ動くとします。x 方向に j 回だけ動くとすると, y 方向に動く回数は m-j です。m 回の動きで, 各々 x 方向に動くか y 方向に動くかの順列は C[m][j] 通りだけあります。
また, x 方向に dx だけ動くためには, 進みたい方向に (j+dx)/2, それとは逆な方向に (j-dx)/2 だけ進めば良いので, この順列は C[j][(j-dx)/2] 通りです。y 方向についても同様にして C[k][(k-dy)/2] (k = m-j) です。

移動の仕方は, 各 j について, 上記の 3 つの数の積の和を取ったものになります。

const ll MOD = 1e9+7;
const int MAX = 200;
ll C[MAX][MAX];

class WolfPackDivTwo {
public:
    int calc(vector <int> X, vector <int> Y, int m) {
        for (int i = 0; i < MAX; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
            }
        }
        int n = X.size();
        ll ans = 0;
        for (int x = -50; x <= 100; x++) for (int y = -50; y <= 100; y++) {
            ll mult = 1;
            for (int i = 0; i < n; i++) {
                int dx = abs(X[i]-x), dy = abs(Y[i]-y);
                int need = dx+dy;
                if (need > m || need%2 != m%2) {
                    mult = 0;
                    break;
                }
                ll sum = 0;
                for (int j = 0; j <= m; j++) {
                    int k = m-j;
                    if (j%2 != dx%2 || j < dx || k%2 != dy%2 || k < dy) continue;
                    ll tmp = C[j][(j-dx)/2];
                    (tmp *= C[k][(k-dy)/2]) %= MOD;
                    (tmp *= C[m][j]) %= MOD;
                    sum += tmp;
                }
                (mult *= sum%MOD) %= MOD;
            }
            (ans += mult) %= MOD;
        }
        return ans;
    }
};