SRM 573 div1 hard: WolfPack - mayoko’s diary

問題

解法

45 度回転させることを考えます。もとの x, y に対して, x' = x+y, y' = x-y とすると, 各移動に対して, x', y' の遷移は以下のようになります。

x++ -> x'++, y'++
x-- -> x'--, y'--
y++ -> x'++, y'--
y-- -> x'--, y'++

これで何に注目すべきかというと, x' の増減と y' の増減は独立したものと考えられるということです。つまり,
「x 軸に対して m 回 ±1 だけ移動してある一つの場所に集まる」という問題と, 「y 軸に対して m 回 ±1 だけ移動してある一つの場所に集まる」という問題に分かれます。

これが分かれば後は div2 hard と同じですね。集まる地点 tx に対して, 今いる地点 x が d だけずれていたとすると, C[m][(m+d)/2] というのが, x にいる頂点の tx に向かう場合の数です。

45 度回転すると x, y について±1 を独立に考えられるというのが面白い問題でした。

const int MAXN = 200000;
const ll MOD = 1e9+7;
ll fact[MAXN], factinv[MAXN];
// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}
// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}
ll nCr(int n, int r) {
    return ((fact[n]*factinv[r])%MOD)*factinv[n-r] % MOD;
}

ll f(const vector<int>& x, int m) {
    int n = x.size();
    ll ret = 0;
    for (int tx = -300000; tx <= 300000; tx++) {
        ll mult = 1;
        for (int i = 0; i < n; i++) {
            int d = abs(tx-x[i]);
            if (d > m || (m+d)%2 == 1) {
                mult = 0;
                break;
            }
            (mult *= nCr(m, (m-d)/2)) %= MOD;
        }
        (ret += mult) %= MOD;
    }
    return ret;
}

class WolfPack {
public:
    int calc(vector <int> xx, vector <int> yy, int m) {
        fact[0] = factinv[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            fact[i] = (fact[i-1]*i)%MOD;
            factinv[i] = mod_inverse(fact[i], MOD);
        }
        int n = xx.size();
        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++) {
            x[i] = xx[i]+yy[i];
            y[i] = xx[i]-yy[i];
        }
        ll ans = f(x, m) * f(y, m) % MOD;
        return (int)(ans);
    }
};