Submission #00135

ソースコード

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
typedef long long ll;
 
struct shop{
    int x, y;
    bool operator<(const shop other) const{
        if(x == x)  return y < other.y;
        else        return x < other.x;
    }
};
 
const ll mod = 1e9+7;
 
ll modpow(ll a, ll b, ll p = 1e9+7){
    if(b == 0)  return 1;
 
    if(b % 2 == 0){
        ll d = modpow(a, b/2, p);
        return (d*d) % p;
    }else{
        return (a%p * modpow(a, b-1, p)) % p;
    }
}
 
struct ModComb{
    vector<ll> po, inv;
    ll N;
 
    ModComb(ll n) : N(n), po(n), inv(n) {
        po[0] = 1;
        for(int i = 1; i < N; i++)  po[i] = (po[i-1] * i) % mod;
        inv[N-1] = modpow(po[N-1], mod-2, mod);
        for(int i = N-2; i >= 0; i--)   inv[i] = (inv[i+1] * (i+1)) % mod;
    }
     
    ll nCk(ll n, ll k){
        if(n < k)   return 0;
        return (((po[n]*inv[n-k])%mod)*inv[k])%mod;
    }
 
    ll nPk(ll n, ll k){
        if(n < k)   return 0;
        return (po[n]*inv[n-k])%mod;
    }
 
    ll nHk(ll n, ll k){
        if(n == 0 && k == 0)    return 1;
        return nCk(n+k-1, k);
    }
};
 
int main(){
    int w, h, n;
    cin >> w >> h >> n;
 
    vector<shop> v;
    int x, y;
     
    v.push_back(shop({0,0}));
    v.push_back(shop({w-1,h-1}));
    for(int i = 0; i < n; i++){
        cin >> x >> y;
        v.push_back(shop({x,y}));
    }
    sort(v.begin(), v.end());
 
    ll ans = 1;
    ModComb mc(200001);
 
    for(int i = 1; i < v.size(); i++){
        int a = v[i].x - v[i-1].x, b = v[i].y - v[i-1].y;
        ans *= mc.nCk(a+b, a);
        ans %= mod;
    }
 
    cout << ans << endl;
 
    return 0;
}

ステータス

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

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
input01.in	AC	23 ms	3676 KB	1
input02.in	AC	28 ms	3460 KB	1
input03.in	AC	25 ms	3508 KB	1
input04.in	AC	21 ms	3552 KB	1
input05.in	AC	22 ms	3716 KB	1
input06.in	AC	28 ms	3628 KB	1
input07.in	AC	29 ms	3672 KB	1
input08.in	AC	22 ms	3708 KB	1
input09.in	AC	28 ms	3620 KB	1
input10.in	AC	25 ms	3536 KB	1
input11.in	AC	22 ms	3572 KB	1
input12.in	AC	33 ms	3608 KB	1
input13.in	AC	27 ms	3644 KB	1
input14.in	AC	25 ms	3552 KB	1
input15.in	AC	27 ms	3596 KB	1
input16.in	AC	29 ms	3636 KB	1
input17.in	AC	35 ms	3672 KB	1
input18.in	AC	35 ms	3588 KB	1
input19.in	AC	29 ms	3504 KB	1
input20.in	AC	28 ms	3672 KB	1
sample.in	AC	33 ms	3716 KB	1