Submission #00187

ソースコード

?
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
typedef long long ll;
const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
#define dump(x) cout << #x << " = " << (x) << endl;
#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 possible(n) cout << ((n) ? "possible" : "impossible" ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto&& (x) : (a) )
#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])
#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) if(1){for(auto tt=x.begin();tt!=x.end();tt++){if(tt!=x.begin())cout<<" ";cout<<(*tt);}cout<<endl;}
#define ALL(obj) (obj).begin(),(obj).end()
#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define EN(x) if(1){cout<<#x<<endl;return 0;}
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
cin>>head;
CINT(move(tail)...);
}
#define CIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
template <class T = ll>
T IN(){T x;cin>>x;return (x);}
template <class Head>
void VT(Head head){}
template <class Head,class Seco,class... Tail>
void VT(Head&& head,Seco&& seco,Tail&&... tail){
seco.resize(head);
VT(head,move(tail)...);
}
void VT2(){}
template <class Head,class... Tail>
void VT2(Head&& head,Tail&&... tail){
VECCIN(head);
VT2(move(tail)...);
}
template <class Head>
void VT3(Head&& head){}
template <class Head,class Seco,class... Tail>
void VT3(Head&& head,Seco&& seco,Tail&&... tail){
seco[head]=IN();
VT3(head,move(tail)...);
}
#define VC1(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);VT2(__VA_ARGS__); //aaabbbccc
#define VC2(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);REP(i,n)VT3(i,__VA_ARGS__); //abcabcabc
// #include <boost/multiprecision/cpp_ll.hpp>
// using namespace boost::multiprecision; // cpp_ll
#define P pair<ll,ll>
#define V vector<ll>
#define M map<ll,ll>
#define S set<ll>
#define pb(a) push_back(a)
#define mp make_pair
ll sqMod(ll x){
return 1LL*x*x%MOD;
}
ll powMod(ll x,ll n){//xのn乗
if(n==0)return 1;
else if(n==1)return x;
if(n%2==0)return (sqMod(powMod(x,n/2)%MOD)%MOD);
else return ((x*sqMod(powMod(x,n/2)%MOD)%MOD)%MOD);
}
V kaitable,gyakutable;
ll ncr(int n,int r){
return 1LL * kaitable[n] * gyakutable[n-r] % MOD * gyakutable[r]% MOD;
}
ll nhr(int n,int r){
return ncr(n+r-1,r);
}
void calcTable(int t){
kaitable = V(t);
gyakutable = V(t);
kaitable[0]=1;
gyakutable[0]=1;
FOR(i,1,t){
kaitable[i] = 1LL * kaitable[i-1] * i % MOD;
gyakutable[i] = powMod(kaitable[i],1e9+5)%MOD;
}
}
signed main(){
CIN(w,h,n);
VC2(n,x,y);
vector<P> p;
p.emplace_back(0,0);
p.emplace_back(w-1,h-1);
REP(i,n)p.emplace_back(x[i],y[i]);
sort(ALL(p));
calcTable(max(h, w) + 5);
ll ans = 1;
REP(i,n+1){
int xd = p[i+1].first - p[i].first;
int yd = p[i+1].second - p[i].second;
ll pat = ncr(xd+yd,xd);
ans *= pat % MOD;
ans %= MOD;
}
COUT(ans);
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input01.in AC 37 ms 604 KB
1
input02.in AC 25 ms 428 KB
1
input03.in AC 26 ms 512 KB
1
input04.in AC 21 ms 584 KB
1
input05.in AC 21 ms 600 KB
1
input06.in AC 23 ms 740 KB
1
input07.in AC 37 ms 1320 KB
1
input08.in AC 40 ms 1264 KB
1
input09.in AC 55 ms 2108 KB
1
input10.in AC 51 ms 2164 KB
1
input11.in AC 164 ms 8372 KB
1
input12.in AC 161 ms 8332 KB
1
input13.in AC 170 ms 8288 KB
1
input14.in AC 167 ms 8376 KB
1
input15.in AC 292 ms 16144 KB
1
input16.in AC 291 ms 16224 KB
1
input17.in AC 309 ms 16172 KB
1
input18.in AC 299 ms 16244 KB
1
input19.in AC 303 ms 16184 KB
1
input20.in AC 299 ms 16256 KB
1
sample.in AC 29 ms 588 KB
1