Submission #00273

ソースコード

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define LCIN(n) LL(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
 
#define FOREACH(x,a) for(auto& (x) : (a) )
 
#define ALL(obj) (obj).begin(),(obj).end()
 
#define P pair<LL,LL>
#define I vector<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())
#define ENDL cout<<endl
 
typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    int from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};
const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
 
int main(){
    CIN(W);CIN(H);CIN(N);
    V<P> vec;
    COMinit();
    REP(a,N){
        CIN(x);CIN(y);
        vec.push_back(P(x,y));
    }
    vec.insert(vec.begin(),P(0,0));
    vec.push_back(P(W-1,H-1));
    sort(ALL(vec));
    LL ans = 1;
    for(int a = 0;a < vec.size()-1;a++){
        ans *= COM(abs(vec.at(a).first-vec.at(a+1).first)+abs(vec.at(a).second - vec.at(a+1).second),abs(vec.at(a).first-vec.at(a+1).first));
        ans %= MOD;
    }
    COUT(ans);
    return 0;
}

ステータス

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

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
input01.in	AC	30 ms	12508 KB	1
input02.in	AC	39 ms	12560 KB	1
input03.in	AC	29 ms	12348 KB	1
input04.in	AC	30 ms	12400 KB	1
input05.in	AC	34 ms	12448 KB	1
input06.in	AC	28 ms	12492 KB	1
input07.in	AC	36 ms	12540 KB	1
input08.in	AC	38 ms	12460 KB	1
input09.in	AC	34 ms	12508 KB	1
input10.in	AC	33 ms	12424 KB	1
input11.in	AC	34 ms	12472 KB	1
input12.in	AC	30 ms	12516 KB	1
input13.in	AC	29 ms	12564 KB	1
input14.in	AC	29 ms	12480 KB	1
input15.in	AC	26 ms	12528 KB	1
input16.in	AC	30 ms	12572 KB	1
input17.in	AC	30 ms	12620 KB	1
input18.in	AC	35 ms	12672 KB	1
input19.in	AC	25 ms	12592 KB	1
input20.in	AC	27 ms	12512 KB	1
sample.in	AC	29 ms	12556 KB	1