Submission #12000788


Source Code Expand

Copy
#include <bits/stdc++.h>
typedef long long int ll;
 
using namespace std;
// {{{ Modint
// using mint = modint<1000000007>;
// mint x = 2;
// std::cout << x.a << std::endl;
template <std::int64_t M>
class modint {
public:
  int64_t a;
 
  explicit constexpr modint(const int64_t x = 0) noexcept :
    a((x % M + M) % M) {}
  constexpr int64_t &value() noexcept { return a; }
  constexpr const int64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    int64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr modint pow(ll t) const {
    if (!t) return modint(1);
    modint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
};
// }}}
using mint = modint<1000000007>;
 
ll Y, X, N;
vector<pair<int, int>> b;
 
mint fact[200000], invfact[200000];
 
// dp[i]: スタートから他のblockを経由しない block i への経路数
mint dp[4000];
 
// block j から block i への経路数
mint route(int j, int i){
  int dy = b[i].first - b[j].first;
  int dx = b[i].second - b[j].second;
  if (dy < 0 || dx < 0)
    return mint(0);
  return fact[dx+dy] * invfact[dx] * invfact[dy];
}
 
// スタートから block i への経路数
mint route(int i){
  int dy = b[i].first;
  int dx = b[i].second;
  return fact[dx+dy] * invfact[dx] * invfact[dy];
}
 
int main() {
  fact[0] = fact[1] = mint(1);
  invfact[0] = invfact[1] = mint(1);
  for (int i=2; i<200000; i++) {
    fact[i] = fact[i-1] * mint(i);
    invfact[i] = mint(1) / fact[i];
  }
 
  cin >> Y >> X >> N;
 
  for (int i=1; i<=N; i++) {
    int y, x;
    cin >> y >> x;
    y--; x--;
    b.emplace_back(y, x);
  }
  b.emplace_back(Y-1, X-1);
  sort(begin(b), end(b));
 
  for (int i=0; i<=N; i++) {
    dp[i] = route(i);
    for (int j=0; j<i; j++) {
      dp[i] -= dp[j] * route(j, i);
    }
  }
 
  cout << dp[N].value() << endl;
  return 0;
}

Submission Info

Submission Time
Task Y - Grid 2
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2882 Byte
Status
Exec Time 104 ms
Memory 3456 KB

Judge Result

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
Case Name Status Exec Time Memory
0_00 34 ms 3328 KB
0_01 34 ms 3328 KB
0_02 35 ms 3328 KB
0_03 34 ms 3328 KB
1_00 34 ms 3328 KB
1_01 34 ms 3328 KB
1_02 34 ms 3328 KB
1_03 34 ms 3328 KB
1_04 34 ms 3328 KB
1_05 56 ms 3456 KB
1_06 103 ms 3456 KB
1_07 101 ms 3456 KB
1_08 104 ms 3456 KB
1_09 56 ms 3456 KB
1_10 95 ms 3456 KB
1_11 93 ms 3456 KB
1_12 96 ms 3456 KB
1_13 96 ms 3456 KB
1_14 95 ms 3456 KB
1_15 96 ms 3456 KB
1_16 96 ms 3456 KB
1_17 95 ms 3456 KB