Submission #00229

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long int
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 1000000007
using namespace std;
ll iy[]={0, 0, 1, -1};
ll ix[]={1, -1, 0, 0};
long long fac[2000010], finv[2000010], inv[2000010];
// テーブルを作る前処理
void nCrinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < 2000010; 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 nCr(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;
}
long long int w, h, n, x[110], y[110], ans;
int main(){
ans = 1;
cin >> w >> h >> n;
x[0]=0;
y[0]=0;
x[n+1]=w-1;
y[n+1]=h-1;
nCrinit();
for(int i=1;i<=n+1;i++){
if(i!=n+1){
cin >> x[i] >> y[i];
ans = (ans * nCr(x[i]-x[i-1]+y[i]-y[i-1], y[i]-y[i-1])) % MOD;
}else{
ans = (ans * nCr(x[i]-x[i-1]+y[i]-y[i-1], y[i]-y[i-1]) )% MOD;
}
}
cout << ans << endl;
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input01.in AC 77 ms 47452 KB
1
input02.in AC 77 ms 47528 KB
1
input03.in AC 80 ms 47344 KB
1
input04.in AC 84 ms 47420 KB
1
input05.in AC 77 ms 47488 KB
1
input06.in AC 64 ms 47432 KB
1
input07.in AC 82 ms 47372 KB
1
input08.in AC 77 ms 47312 KB
1
input09.in AC 62 ms 47384 KB
1
input10.in AC 63 ms 47328 KB
1
input11.in AC 66 ms 47392 KB
1
input12.in AC 70 ms 47468 KB
1
input13.in AC 64 ms 47412 KB
1
input14.in AC 65 ms 47480 KB
1
input15.in AC 72 ms 47556 KB
1
input16.in AC 64 ms 47496 KB
1
input17.in AC 69 ms 47436 KB
1
input18.in AC 63 ms 47380 KB
1
input19.in AC 71 ms 47324 KB
1
input20.in AC 69 ms 47396 KB
1
sample.in AC 73 ms 47340 KB
1