Submission #00079

ソースコード

100

101

102

#include <bits/stdc++.h>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
 
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair
 
 
const int MAXN = 1010000;
 
vl fact(MAXN);
vl rfact(MAXN);
 
ll mod_pow(ll x, ll p, ll M = MOD) {
        ll a = 1;
        while (p) {
                if (p % 2)
                        a = a*x%M;
                x = x*x%M;
                p /= 2;
        }
        return a;
}
 
ll mod_inverse(ll a, ll M = MOD) {
        return mod_pow(a, M - 2, M);
}
 
void set_fact(ll n, ll M = MOD) {
        fact[0] = fact[1] = rfact[0] = rfact[1] = 1;
        for (ll i = 2; i <= n; i++) {
                fact[i] = i * fact[i - 1] % M;
                rfact[i] = mod_inverse(fact[i], M);
        }
}
 
//http://drken1215.hatenablog.com/entry/2018/06/08/210000
//nが大きくfactが計算できないときのほかの計算方法について書いてある
ll nCr(ll n, ll r, ll M = MOD) {
  if (r > n) return 0;
  ll ret = fact[n];
  ret = (ret*rfact[r]) % M;
  ret = (ret*rfact[n - r]) % M;
  return ret;
}
 
int main() {
  set_fact(MAXN - 5);
  int w, h, n;
  cin >> w >> h >> n;
  vi x(n), y(n);
  rep (i, n) {
    cin >> x[i] >> y[i];
  }
  x.push_back(w - 1);
  y.push_back(h - 1);
  int nowx = 0, nowy = 0;
  ll ans = 1;
  rep (i, x.size()) {
    int nexx = x[i], nexy = y[i];
    int diffx = nexx - nowx, diffy = nexy - nowy;
    ans = ans * nCr(diffx + diffy, diffx) % MOD;
    nowx = nexx; nowy = nexy;
  }
  cout << ans << endl;
}

ステータス

項目	データ
問題	0006 - 寄り道
ユーザー名	fuppy
投稿日時	2018-11-24 14:25:04
言語	C++14
状態	Accepted
得点	400
ソースコード長	3135 Byte
最大実行時間	474 ms
最大メモリ使用量	16448 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
input01.in	AC	429 ms	16344 KB	1
input02.in	AC	424 ms	16148 KB	1
input03.in	AC	433 ms	16204 KB	1
input04.in	AC	466 ms	16260 KB	1
input05.in	AC	434 ms	16188 KB	1
input06.in	AC	431 ms	16244 KB	1
input07.in	AC	419 ms	16304 KB	1
input08.in	AC	428 ms	16368 KB	1
input09.in	AC	429 ms	16292 KB	1
input10.in	AC	423 ms	16348 KB	1
input11.in	AC	434 ms	16404 KB	1
input12.in	AC	437 ms	16204 KB	1
input13.in	AC	428 ms	16260 KB	1
input14.in	AC	433 ms	16448 KB	1
input15.in	AC	434 ms	16372 KB	1
input16.in	AC	474 ms	16424 KB	1
input17.in	AC	434 ms	16344 KB	1
input18.in	AC	423 ms	16276 KB	1
input19.in	AC	435 ms	16332 KB	1
input20.in	AC	438 ms	16252 KB	1
sample.in	AC	427 ms	16184 KB	1