test/AOJ/1501-Grid.test.cpp

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1501"
#include <bits/stdc++.h>

#include "../../Math/Modulo/mod-int.hpp"

#include "../../Math/Combinatorics/factorials.hpp"
#include "../../Math/Combinatorics/binomial-O(K).cpp"
#include "../../Math/Combinatorics/binomial-table-O(NN).cpp"
#include "../../Math/Combinatorics/binomial-table-const-N.cpp"

#include "../../Util/IO/var-declaration-with-input.hpp"
#include "../../Util/chminmax.hpp"
#include "../../Util/int-infinity.hpp"
#include "../../Util/Debug/debug.hpp"

using namespace std;

int main() {
    constexpr int OFFSET = 2000;
    constexpr int MOD = int(1e8) + 7;
    using Mint = StaticModInt<MOD>;
    const auto F = Factorials<Mint>();

    var(int, H, W, sy, sx, gy, gx);
    sx += OFFSET;
    sy += OFFSET;
    gx += OFFSET;
    gy += OFFSET;

    const auto manhattan = [](auto y1, auto x1, auto y2, auto x2) { return abs(y1 - y2) + abs(x1 - x2); };

    int minDist = INF;

    for (const int ay : {-H, 0, +H}) {
        for (const int ax : {-W, 0, +W}) {
            chmin(minDist, manhattan(sy, sx, gy + ay, gx + ax));
        }
    }

    const auto allEqual = [](std::initializer_list<Mint> xs) {
        for (const auto& e : xs)
            if (e != *begin(xs)) return false;
        return true;
    };

    Mint ans = 0;
    for (const int ay : {-H, 0, +H}) {
        for (const int ax : {-W, 0, +W}) {
            if (manhattan(sy, sx, gy + ay, gx + ax) != minDist) continue;

            const int h = abs(sy - (gy + ay));
            const int w = abs(sx - (gx + ax));

            const auto res1 = F.fact(h + w) * F.finv(h) * F.finv(w);
            const auto res2 = F.fact(h + w) / (F.fact(h) * F.fact(w));
            const auto res3 = F.C(h + w, h);
            const auto res4 = F.C(h + w, w);
            const auto res5 = binomial<Mint>(h + w, h);
            const auto res6 = binomialTable<Mint>(h + w)[h + w][h];
            const auto res7 = binomialTable_constN<Mint>(h + w, h)[h];

            dump(res1, res2, res3, res4, res5, res6, res7);

            assert(allEqual({res1, res2, res3, res4, res5, res6, res7}));
            ans += res1;
        }
    }

    cout << ans << endl;

    return 0;
}

#line 1 "test/AOJ/1501-Grid.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1501"
#include <bits/stdc++.h>

#line 6 "Math/Modulo/mod-int.hpp"

/**
 * @brief Mod-Int (コンパイル時mod型と実行時mod型)
 */
namespace internal {

template <class ModHolder>
class ModInt {
private:
    int64_t value;

public:
    constexpr ModInt() noexcept
        : value(0) {}

    constexpr ModInt(int64_t v) noexcept
        : value(ModInt::normalized(v)) {}

    static constexpr const ModInt raw(int64_t v) noexcept {
        ModInt ret;
        ret.value = v;
        return ret;
    }

    static constexpr ModInt nullopt() noexcept { return ModInt::raw(std::numeric_limits<int64_t>::min()); }

    constexpr bool isNull() const noexcept { return *this == ModInt::nullopt(); }

    static constexpr int64_t mod() { return ModHolder::mod; }

    static int64_t setMod(int64_t m) noexcept {
        assert(m >= 1);
        return ModHolder::mod = m;
    }

    template <class T>
    constexpr explicit operator T() const noexcept {
        return static_cast<T>(value);
    }

    constexpr int64_t val() const noexcept { return value; }

    constexpr ModInt& operator+=(const ModInt& rhs) noexcept {
        if ((value += rhs.value) >= mod()) value -= mod();
        return *this;
    }
    constexpr ModInt& operator-=(const ModInt& rhs) noexcept {
        if ((value -= rhs.value) < 0) value += mod();
        return *this;
    }
    constexpr ModInt& operator*=(const ModInt& rhs) noexcept {
        (value *= rhs.value) %= mod();
        return *this;
    }
    constexpr ModInt& operator/=(const ModInt& rhs) noexcept { return *this *= rhs.inv(); }
    constexpr const ModInt inv() const noexcept { return ModInt(ModInt::inverse(value, mod())); }
    constexpr const ModInt operator+() const noexcept { return *this; }
    constexpr const ModInt operator-() const noexcept { return ModInt(-value); }

    constexpr const ModInt pow(int64_t expv) const noexcept {
        int64_t ret = 1, square = value;
        for (uint64_t p = std::abs(expv); p; p >>= 1) {
            if (p & 1) (ret *= square) %= mod();
            (square *= square) %= mod();
        }
        return (expv < 0) ? (ModInt::raw(1) / ModInt::raw(ret)) : ModInt::raw(ret);
    }

    friend constexpr bool operator==(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.value == rhs.value; }
    friend constexpr bool operator!=(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.value != rhs.value; }
    friend constexpr const ModInt operator+(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) += rhs; }
    friend constexpr const ModInt operator-(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) -= rhs; }
    friend constexpr const ModInt operator*(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) *= rhs; }
    friend constexpr const ModInt operator/(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) /= rhs; }

    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) {
#ifdef LOCAL_DEBUG
        if (x.isNull()) return os << "{nullopt}";
#endif
        return os << x.value;
    }

    friend std::istream& operator>>(std::istream& is, ModInt& x) {
        is >> x.value;
        x.value = ModInt::normalized(x.value);
        return is;
    }

private:
    static constexpr int64_t normalized(int64_t n) {
        n = (-mod() <= n && n < mod() ? n : n % mod());
        if (n < 0) n += mod();
        return n;
    }

    static constexpr int64_t inverse(int64_t a, int64_t m) {
        int64_t u = 0, v = 1;
        while (a != 0) {
            const auto t = m / a;
            static_cast<void>(m -= t * a), std::swap(m, a);
            static_cast<void>(u -= t * v), std::swap(u, v);
        }
        assert(m == 1);
        return u;
    }
};

template <int64_t Mod>
struct StaticModHolder {
    static constexpr int64_t mod = Mod;
};

template <int ID>
struct DynamicModHolder {
    static int64_t mod;
};
template <int ID>
int64_t DynamicModHolder<ID>::mod;

}  // namespace internal

template <int64_t Mod>
using StaticModInt = internal::ModInt<internal::StaticModHolder<Mod>>;

using ModInt1000000007 = StaticModInt<int(1e9) + 7>;
using ModInt998244353 = StaticModInt<998244353>;

template <int ID>
using DynamicModInt = internal::ModInt<internal::DynamicModHolder<ID>>;
#line 5 "test/AOJ/1501-Grid.test.cpp"

#line 4 "Math/Combinatorics/factorials.hpp"

#line 6 "Math/Combinatorics/factorials.hpp"

/**
 * @brief factorials (階乗, 階乗の逆元, nCr, nPr)
 */
template <class Mint>
struct Factorials {
public:
    using value_type = Mint;
    static constexpr size_t MAX_N = std::min<size_t>(1e7, Mint::mod()) + 1;

private:
    mutable std::vector<value_type> m_fact, m_finv;

public:
    Factorials() {
        m_fact.reserve(MAX_N);
        m_finv.reserve(MAX_N);
        m_fact.resize(2, value_type::raw(1));   // m_fact[0] = m_fact[1] = 1
        m_finv.resize(2, value_type::raw(1));   // m_finv[0] = m_finv[1] = 1
    }

    void preCalc(size_t n) const {
        if (n < m_fact.size()) return;
        const size_t l = m_fact.size();
        const size_t r = n + 1;
        m_fact.resize(r), m_finv.resize(r);
        for (size_t i = l; i < r; ++i) m_fact[i] = m_fact[i - 1] * i;
        m_finv[r - 1] = m_fact[r - 1].inv();
        for (size_t i = r - 1; i > l; --i) m_finv[i - 1] = m_finv[i] * i;
    }

    const value_type fact(int i) const { return preCalc(i), m_fact[i]; }
    const value_type finv(int i) const { return preCalc(i), m_finv[i]; }

    const value_type C(int n, int r) const {
        if (r < 0 || n < r) return value_type::raw(0);
        return preCalc(n), m_fact[n] * m_finv[r] * m_finv[n - r];
    }

    const value_type P(int n, int r) const {
        if (r < 0 || n < r) return value_type::raw(0);
        return preCalc(n), m_fact[n] * m_finv[n - r];
    }

    const value_type H(int n, int r) const {
        if (n < 0 || r < 0) return value_type::raw(0);
        if (n == 0 && r == 0) return value_type::raw(1);
        return C(n + r - 1, r);
    }
};
#line 3 "Math/Combinatorics/binomial-O(K).cpp"

/**
 * @brief binomial() (二項係数 $O(K)$)
 */
template <class T>
T binomial(int64_t n, int k) {
    if (k < 0 || n < k) return 0;
    T nume = 1, deno = 1;
    for (int i = 1; i <= k; ++i) {
        nume *= n - i + 1;
        deno *= i;
    }
    return nume / deno;
}
#line 3 "Math/Combinatorics/binomial-table-O(NN).cpp"

/**
 * @brief binomialTable() (二項係数テーブル $O(N^2)$)
 * パスカルの三角形により N 以下の二項係数を求める。
 */
template <class T>
auto binomialTable(int N) {
    using std::vector;
    vector<vector<T>> binomial(N + 1);
    for (int i = 0; i <= N; ++i) {
        binomial[i].resize(i + 1);
        for (int j = 0; j <= i; ++j) {
            if (j == 0 || j == i)
                binomial[i][j] = 1;
            else
                binomial[i][j] = binomial[i - 1][j - 1] + binomial[i - 1][j];
        }
    }
    return binomial;
}
#line 4 "Math/Combinatorics/binomial-table-const-N.cpp"

/**
 * @brief binomialTable_constN() (二項係数テーブル $O(K)$)
 * binomial[k] = binomial(N, k) を O(K) で前計算する。
 */
template <class T>
std::vector<T> binomialTable_constN(int64_t N, int K) {
    std::vector<T> binomial(K + 1);
    binomial[0] = 1;
    for (int i = 1; i <= K; ++i) {
        binomial[i] = binomial[i - 1] * (N - i + 1) / i;
    }
    return binomial;
}
#line 10 "test/AOJ/1501-Grid.test.cpp"

#line 3 "Util/IO/var-declaration-with-input.hpp"

/**
 * @brief 複数変数宣言をして同時に入力もするやつ
 */
template <class T>
std::istream& operator,(std::istream& is, T& rhs) {
    return is >> rhs;
}

#define var(type, ...) \
    type __VA_ARGS__;  \
    std::cin >> __VA_ARGS__
#line 2 "Util/chminmax.hpp"

/**
 * @brief chmin(), chmax()
 */
template <class T, class U>
inline bool chmin(T& a, const U& b) {
    return b < a && (a = b, true);
}

template <class T, class U>
inline bool chmax(T& a, const U& b) {
    return b > a && (a = b, true);
}
#line 3 "Util/int-infinity.hpp"

/**
 * @brief int-infinity (整数のデカイ値)
 * 2倍してもオーバーフローしない & memset()にも使える (需要ある？)
 */
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
#line 5 "Util/Debug/debug.hpp"

#line 7 "Util/Debug/debug.hpp"

/**
 * @brief Debug
 */
#ifdef LOCAL_DEBUG

namespace dbg {

int w_ = 4;
bool negativeValAsNull_ = true;
std::ostream* os = &std::cerr;

template <class T, std::enable_if_t<!std::is_arithmetic<T>::value, std::nullptr_t> = nullptr>
void put(const T& x) {
    *os << std::setw(w_) << x;
}
template <class T, std::enable_if_t<std::is_signed<T>::value, std::nullptr_t> = nullptr>
void put(const T& x) {
    if (x <= -INF)
        *os << std::setw(w_) << "-INF";
    else if (negativeValAsNull_ && x < 0)
        *os << std::setw(w_) << " - ";
    else if (x >= INF)
        *os << std::setw(w_) << "INF";
    else
        *os << std::setw(w_) << x;
}
template <class T, std::enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr>
void put(const T& x) {
    if (static_cast<int64_t>(x) >= static_cast<int64_t>(INF))
        *os << std::setw(w_) << "INF";
    else
        *os << std::setw(w_) << x;
}
template <class A, class B>
void put(const std::pair<A, B>& t) {
    *os << '(' << std::setw(w_) << std::get<0>(t) << ",  " << std::setw(w_) << std::get<1>(t) << ')';
}
template <class A, class B, class C>
void put(const std::tuple<A, B, C>& t) {
    *os << '(' << std::setw(w_) << std::get<0>(t) << ",  " << std::setw(w_) << std::get<1>(t) << ",  " << std::setw(w_) << std::get<2>(t) << ')';
}

template <class Arr>
void showArrayH__(const Arr& a, size_t begin, size_t end) {
    for (size_t i = begin; i < end; ++i) *os << '[' << std::setw(dbg::w_) << i << "] ";
    *os << '\n';
    for (size_t i = begin; i < end; ++i) *os << ' ', dbg::put(a[i]), *os << "  ";
    *os << '\n';
}
template <class Arr>
void showArrayV__(const Arr& a, size_t begin, size_t end) {
    for (size_t i = begin; i < end; ++i)
        *os << '[' << std::setw(2) << i << ']', dbg::put(a[i]), *os << "\n";
    *os << std::flush;
}
template <class Table>
void showTable__(const Table& t, size_t yBegin, size_t yEnd, size_t xBegin, size_t xEnd) {
    *os << std::string(1 + 2 + 1, ' ');
    for (size_t j = xBegin; j < xEnd; ++j) *os << '[' << std::setw(dbg::w_) << j << "] ";
    *os << '\n';

    for (size_t i = yBegin; i < yEnd; ++i) {
        *os << '[' << std::setw(2) << i << "]";
        for (size_t j = xBegin; j < xEnd; ++j) *os << ' ', dbg::put(t[i][j]), *os << "  ";
        *os << '\n';
    }
}

}  // namespace dbg

void debug_setw(int w) {
    dbg::w_ = w;
}
void debug_negativeValAsNull(bool f) {
    dbg::negativeValAsNull_ = f;
}
void debug_setOstream(std::ostream& os) {
    dbg::os = &os;
}
void debug_hr() {
    *dbg::os << "----------------------------------------------------------------------\n";
}
void debug_println() {
    *dbg::os << std::endl;
}
template <class Head, class... Tail>
void debug_println(const Head& head, const Tail&... tail) {
    dbg::put(head);
    debug_println(tail...);
}

#define putDbgPrefix() *dbg::os << __func__ << '(' << std::setfill('0') << std::setw(3) << __LINE__ << std::setfill(' ') << "): "
#define showArrayH(a, beginIdx, endIdx) (void)(putDbgPrefix() << #a << ":\n"), dbg::showArrayH__(a, beginIdx, endIdx)
#define showArrayV(a, beginIdx, endIdx) (void)(putDbgPrefix() << #a << ":\n"), dbg::showArrayV__(a, beginIdx, endIdx)
#define showTable(t, yBegin, yEnd, xBegin, xEnd) (void)(putDbgPrefix() << #t << ":\n"), dbg::showTable__(t, yBegin, yEnd, xBegin, xEnd)
#define dbgMsg_(x) "  |  " #x " = ", x
#define dump1(a) (void)(putDbgPrefix()), debug_println(#a " = ", a)
#define dump2(a, b) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b))
#define dump3(a, b, c) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c))
#define dump4(a, b, c, d) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c), dbgMsg_(d))
#define dump5(a, b, c, d, e) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c), dbgMsg_(d), dbgMsg_(e))
#define dump6(a, b, c, d, e, f) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c), dbgMsg_(d), dbgMsg_(e), dbgMsg_(f))
#define dump7(a, b, c, d, e, f, g) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c), dbgMsg_(d), dbgMsg_(e), dbgMsg_(f), dbgMsg_(g))
#define GET_8TH_ARG(dummy1, dummy2, dummy3, dummy4, dummy5, dummy6, dumy7, NAME, ...) NAME
#define dump(...) GET_8TH_ARG(__VA_ARGS__, dump7, dump6, dump5, dump4, dump3, dump2, dump1)(__VA_ARGS__)

#else

#define debug_setw(...) ((void)0)
#define debug_negativeValAsNull(...) ((void)0)
#define debug_setOstream(...) ((void)0)
#define debug_hr(...) ((void)0)
#define debug_println(...) ((void)0)
#define showArrayH(...) ((void)0)
#define showArrayV(...) ((void)0)
#define showTable(...) ((void)0)
#define dump(...) ((void)0)

#endif
#line 15 "test/AOJ/1501-Grid.test.cpp"

using namespace std;

int main() {
    constexpr int OFFSET = 2000;
    constexpr int MOD = int(1e8) + 7;
    using Mint = StaticModInt<MOD>;
    const auto F = Factorials<Mint>();

    var(int, H, W, sy, sx, gy, gx);
    sx += OFFSET;
    sy += OFFSET;
    gx += OFFSET;
    gy += OFFSET;

    const auto manhattan = [](auto y1, auto x1, auto y2, auto x2) { return abs(y1 - y2) + abs(x1 - x2); };

    int minDist = INF;

    for (const int ay : {-H, 0, +H}) {
        for (const int ax : {-W, 0, +W}) {
            chmin(minDist, manhattan(sy, sx, gy + ay, gx + ax));
        }
    }

    const auto allEqual = [](std::initializer_list<Mint> xs) {
        for (const auto& e : xs)
            if (e != *begin(xs)) return false;
        return true;
    };

    Mint ans = 0;
    for (const int ay : {-H, 0, +H}) {
        for (const int ax : {-W, 0, +W}) {
            if (manhattan(sy, sx, gy + ay, gx + ax) != minDist) continue;

            const int h = abs(sy - (gy + ay));
            const int w = abs(sx - (gx + ax));

            const auto res1 = F.fact(h + w) * F.finv(h) * F.finv(w);
            const auto res2 = F.fact(h + w) / (F.fact(h) * F.fact(w));
            const auto res3 = F.C(h + w, h);
            const auto res4 = F.C(h + w, w);
            const auto res5 = binomial<Mint>(h + w, h);
            const auto res6 = binomialTable<Mint>(h + w)[h + w][h];
            const auto res7 = binomialTable_constN<Mint>(h + w, h)[h];

            dump(res1, res2, res3, res4, res5, res6, res7);

            assert(allEqual({res1, res2, res3, res4, res5, res6, res7}));
            ans += res1;
        }
    }

    cout << ans << endl;

    return 0;
}