Submission #00129

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pdd=pair<double,double>;
using pdl=pair<double,ll>;
const ll LINF=0x3fffffffffffffff;
const ll MOD=1000000007;
const ll MODD=0x3b800001;
const int INF=0x3fffffff;
const double DINF=numeric_limits<double>::infinity();
const vector<pii> four={{1,0},{0,1},{-1,0},{0,-1}};
#define _overload4(_1,_2,_3,_4,name,...) name
#define _overload3(_1,_2,_3,name,...) name
#define _rep1(n) _rep2(i,n)
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(ll i=a;i<b;++i)
#define _rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) _overload4(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define _rrep1(n) _rrep2(i,n)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(ll i=b-1;i>=a;i--)
#define _rrep4(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) _overload4(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i:a)
#define sum(...) accumulate(range(__VA_ARGS__),0LL)
#define _range(i) (i).begin(),(i).end()
#define _range2(i,k) (i).begin(),(i).begin()+k
#define _range3(i,a,b) (i).begin()+a,(i).begin()+b
#define range(...) _overload3(__VA_ARGS__,_range3,_range2,_range)(__VA_ARGS__)
#define Yes(i) out(i?"Yes":"No")
#define YES(i) out(i?"YES":"NO")
//#define START auto start=system_clock::now()
//#define END auto end=system_clock::now();cerr<<duration_cast<milliseconds>(end-start).count()<<" ms\n"
#define elif else if
#define unless(a) if(!(a))
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__));in(name)
__attribute__((constructor)) void SETTINGS(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};
template<class T>
inline constexpr T gcd (T a,T b) {if(a==b)return a;else return gcd(b,(a-1)%b+1);}
template<class T>
inline constexpr T lcm (T a,T b) {a*b/gcd(a,b);}
template<class T>
inline constexpr T min(vector<T>& v){return *min_element(range(v));}
inline char min(string& v){return *min_element(range(v));}
template<class T>
inline constexpr T max(vector<T>& v){return *max_element(range(v));}
inline char max(string& v){return *max_element(range(v));}
template<typename T>
inline bool update_min(T& mn,const T& cnt){if(mn>cnt){mn=cnt;return 1;}else return 0;}
template<typename T>
inline bool update_max(T& mx,const T& cnt){if(mx<cnt){mx=cnt;return 1;}else return 0;}
inline void in() {}
template<class T>
istream& operator >> (istream& is, vector<T>& vec);
template<class T,size_t size>
istream& operator >> (istream& is, array<T,size>& vec);
template<class T,class L>
istream& operator >> (istream& is, pair<T,L>& p);
template<class T>
ostream& operator << (ostream& os, vector<T>& vec);
template<class T,class L>
ostream& operator << (ostream& os, pair<T,L>& p);
template<class T>
istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;}
template<class T,class L>
istream& operator >> (istream& is, pair<T,L>& p){is >> p.first;is >> p.second;return is;}
template<class T>
ostream& operator << (ostream& os, vector<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;}
template<class T>
ostream& operator << (ostream& os, deque<T>& deq){os << deq[0];rep(i,1,deq.size()){os << ' ' << deq[i];}return os;}
template<class T,class L>
ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;}
template <class Head, class... Tail>
inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);}
template <class T>
inline void out(T t){cout<<t<<'\n';}
inline void out(){cout<<'\n';}
template <class Head, class... Tail>
inline void out(Head head,Tail... tail){cout<<head<<' ';out(move(tail)...);}
template <class T>
inline void err(T t){cerr<<t<<'\n';}
inline void err(){cerr<<'\n';}
template <class Head, class... Tail>
inline void err(Head head,Tail... tail){cerr<<head<<' ';out(move(tail)...);}
ll extgcd(ll a, ll b, ll &x, ll &y) { //ax + by = gcd(x,y)
ll g = a; x = 1; y = 0;
if (b != 0){
g = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
return g;
}
ll invmod(ll a, ll m) { // 1/a (mod m)
ll x, y;
if (extgcd(a, m, x, y) == 1) return (x + m) % m;
else return 0; // unsolvable
}
ll comb(ll n,ll r){
if(2*r>n)return comb(n,n-r);
ll ans=1;
rep(i,n-r+1,n+1)ans=ans*i%MOD;
rep(i,1,r+1)ans=ans*invmod(i,MOD)%MOD;
return ans;
}
ll pascal(ll a,ll b){return comb(a+b,a);}
signed main(){
LL(w,h,n);
ll lastx=0,lasty=0;
ll ans=1;
rep(n){
LL(x,y);
ans=ans*pascal(x-lastx,y-lasty)%MOD;
lastx=x;
lasty=y;
}
ans=ans*pascal(w-1-lastx,h-1-lasty)%MOD;
out(ans);
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input01.in AC 32 ms 604 KB
1
input02.in AC 20 ms 564 KB
1
input03.in AC 21 ms 648 KB
1
input04.in AC 25 ms 604 KB
1
input05.in AC 20 ms 432 KB
1
input06.in AC 19 ms 516 KB
1
input07.in AC 24 ms 600 KB
1
input08.in AC 24 ms 552 KB
1
input09.in AC 28 ms 628 KB
1
input10.in AC 32 ms 452 KB
1
input11.in AC 75 ms 532 KB
1
input12.in AC 71 ms 608 KB
1
input13.in AC 28 ms 556 KB
1
input14.in AC 27 ms 640 KB
1
input15.in AC 147 ms 600 KB
1
input16.in AC 118 ms 556 KB
1
input17.in AC 128 ms 504 KB
1
input18.in AC 120 ms 588 KB
1
input19.in AC 126 ms 540 KB
1
input20.in AC 126 ms 612 KB
1
sample.in AC 24 ms 696 KB
1