Submission #00218

ソースコード

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
 
using i64 = int64_t;
const int M = 3e6;
const i64 mod = 1e9 + 7;
vector<i64> fac(M), inv(M);
 
i64 modpow(i64 a, i64 x) {
  if (x == 0) {
    return 1;
  } else if (x == 1) {
    return a;
  } else if (x & 1) {
    return a * modpow(a, x - 1) % mod;
  } else {
    return modpow(a * a % mod, x / 2);
  }
}
 
i64 cmb(int n, int r) { return fac[n] * inv[r] % mod * inv[n - r] % mod; }
 
int main() {
 
  fac[0] = fac[1] = 1;
  for (int i = 2; i < M; i++) {
    fac[i] = fac[i - 1] * i % mod;
  }
  rep(i, M) inv[i] = modpow(fac[i], mod - 2);
 
  int h, w, n;
  cin >> h >> w >> n;
  vector<pair<int, int>> v(n);
  rep(i, n) cin >> v[i].first >> v[i].second;
  v.push_back({w - 1, h - 1});
  auto pre = make_pair(0, 0);
  i64 ans = 1;
  for (auto p : v) {
    assert(pre.first <= p.first);
    assert(pre.second <= p.second);
    auto a = p.first - pre.first, b = p.second - pre.second;
    (ans *= cmb(a + b, a)) %= mod;
    pre = p;
  }
  cout << ans << endl;
  return 0;
}

ステータス

項目	データ
問題	0006 - 寄り道
ユーザー名	ia7ck
投稿日時	2018-11-24 15:33:54
言語	C++14
状態	Runtime Error
得点	0
ソースコード長	1172 Byte
最大実行時間	1688 ms
最大メモリ使用量	47480 KB

セット

	セット	得点	Cases
1	ALL	0 / 400	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
input01.in	AC	419 ms	47452 KB	1
input02.in	AC	426 ms	47260 KB	1
input03.in	AC	425 ms	47324 KB	1
input04.in	RE	1688 ms	47388 KB	1
input05.in	RE	437 ms	47320 KB	1
input06.in	AC	451 ms	47380 KB	1
input07.in	RE	428 ms	47440 KB	1
input08.in	RE	444 ms	47372 KB	1
input09.in	AC	423 ms	47424 KB	1
input10.in	AC	441 ms	47356 KB	1
input11.in	AC	422 ms	47416 KB	1
input12.in	AC	412 ms	47480 KB	1
input13.in	RE	451 ms	47416 KB	1
input14.in	RE	444 ms	47476 KB	1
input15.in	AC	425 ms	47412 KB	1
input16.in	AC	415 ms	47348 KB	1
input17.in	AC	432 ms	47412 KB	1
input18.in	AC	449 ms	47348 KB	1
input19.in	AC	431 ms	47412 KB	1
input20.in	AC	424 ms	47352 KB	1
sample.in	AC	429 ms	47412 KB	1