AtCoder AGC 001 E - BBQ Hard (1400 点)

当時は解けなかったけど、二項係数を扱うスキルを格段に高めた今なら解ける！！！

というのは罠で、「経路数に帰着する」という考え方をこの問題で学んだ ^^;

問題へのリンク

問題概要

個の正の整数値のペア が与えられる。

• 

の値を 10⁹ + 7 で割ったあまりを求めよ。

制約

• 
• 

考えたこと

二項係数に関する問題はとにかく経路数に帰着してみるといいことがあったりするっぽい。下図は editorial 引用。

赤丸や青丸はそれぞれ座標 を表している。ここで、求めたい値は概ね

• 赤丸と青丸の各ペアについての道順の個数

を表している。よって多点スタート多点ゴールの経路数え上げを行えば良い。ここにかかる計算量は、登場する要素値の絶対値の最大値を として で済んで間に合う。

ただし罠があって

• 同一の を表す赤青ペアもカウントしてしまうので別途求めて引く (適切な前処理後、 でできる)
• 最後に 2 で割る

という風にすれば OK。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;

int main() {
    BiCoef<mint> bc(11000);
    int N; cin >> N;
    using pint = pair<int,int>;
    map<pint,int> ma;
    for (int i = 0; i < N; ++i) {
        int x, y; cin >> x >> y;
        ma[pint(x, y)]++;
    }

    const int GETA = 2500;
    vector<vector<mint> > dp(GETA*2, vector<mint>(GETA*2, 0));
    for (auto it : ma)
        dp[GETA - it.first.first][GETA - it.first.second] = it.second;
    for (int i = 1; i < dp.size(); ++i) 
        for (int j = 1; j < dp[0].size(); ++j) 
            dp[i][j] += dp[i-1][j] + dp[i][j-1];

    mint res = 0;
    for (auto it : ma)
        res += dp[it.first.first + GETA][it.first.second + GETA] * it.second;
    for (auto it : ma)
        res -= bc.com(it.first.first*2 + it.first.second*2, it.first.first*2) * it.second;
    cout << res * bc.inv(2) << endl;
}