#include <bits/stdc++.h>
#define int __int128_t
#define fi first
#define se second
using namespace std;
const int MAXN = 6e5 + 11;
int phi = 1;
map<int, int> pf;
map<int, int> f[MAXN];
int pm(int a, int b, int Z){
a %= Z;
if(b == 0) return 1;
return pm(a * a % Z, b / 2, Z) * (b % 2 ? a : 1) % Z;
}
int mi(int a, int Z){
assert(__gcd(a, Z) == 1);
a %= Z;
return pm(a, phi - 1, Z);
}
int C(int n, int r, int Z){
if(n < r || r < 0) return 0;
map<int, int> res; res[0] = 1;
for(auto i : f[n]){
if(i.fi == 0){
res[0] = (res[0] * i.se) % Z;
}else{
res[i.fi] += i.se;
}
}
for(auto i : f[r]){
if(i.fi == 0){
res[0] = (res[0] * mi(i.se, Z)) % Z;
}else{
res[i.fi] -= i.se;
}
}
for(auto i : f[n - r]){
if(i.fi == 0){
res[0] = (res[0] * mi(i.se, Z)) % Z;
}else{
res[i.fi] -= i.se;
}
}
int ans = 1;
for(auto i : res){
if(i.fi == 0){
ans *= i.se;
continue;
}
for(int j = 0; j < i.se; j++){
ans *= i.fi; ans %= Z;
}
}
return ans;
}
int p[25][2], d[25][25];
int Cu[25];
int32_t main(){
int64_t N, M, K, T, Z;
cin >> N >> M >> K >> T >> Z;
phi = Z;
int z = Z;
for(int i = 2; i <= sqrt(1e9) + 11; i++){
if(z % i == 0) phi = phi / i * (i - 1);
while(z % i == 0) pf[i]++, z /= i;
}
if(z != 1) phi = phi / z * (z - 1), pf[z]++;
f[0][0] = 1;
for(int i = 1; i <= MAXN - 1; i++){
f[i] = f[i - 1];
int x = i;
for(auto p : pf){
while(x % p.fi == 0){
f[i][p.fi]++; x /= p.fi;
}
}
f[i][0] = f[i - 1][0] * x % Z;
}
p[0][0] = 0, p[0][1] = 0;
p[K + 1][0] = N, p[K + 1][1] = M;
vector<pair<int, int>> v;
for(int i = 0; i < K; i++){
int64_t x, y; cin >> x >> y;
v.push_back({x, y});
}
sort(v.begin(), v.end());
for(int i = 1; i <= K; i++){
p[i][0] = v[i - 1].fi, p[i][1] = v[i - 1].se;
}
for(int i = 0; i <= K + 1; i++){
for(int j = 0; j <= K + 1; j++){
int dx = p[j][0] - p[i][0];
int dy = p[j][1] - p[i][1];
d[i][j] = C(dx + dy, dx, Z);
}
}
for(int i = 0; i <= K; i++){
Cu[i] = C(i, T + 1, Z);
}
int s = C(N + M, N, Z), t = 0;
for(int i = 0; i < (1 << K); i++){
int U = __builtin_popcount(i);
int f = 1, pv = 0;
for(int j = 0; j < K; j++){
if(i & (1 << j)){
f = f * d[pv][j + 1] % Z;
pv = j + 1;
}
}
f = f * d[pv][K + 1] % Z;
t += ((U + T + 1) % 2 ? -1 : 1) * Cu[U] * f % Z;
t %= Z;
}
cout << (long long)((s - t) % Z + Z) % Z << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
169352 KB |
Output is correct |
| 2 |
Incorrect |
164 ms |
169272 KB |
Output isn't correct |
| 3 |
Correct |
118 ms |
121156 KB |
Output is correct |
| 4 |
Correct |
105 ms |
98832 KB |
Output is correct |
| 5 |
Correct |
224 ms |
121204 KB |
Output is correct |
| 6 |
Incorrect |
88 ms |
99004 KB |
Output isn't correct |
| 7 |
Correct |
109 ms |
99020 KB |
Output is correct |
| 8 |
Correct |
87 ms |
98808 KB |
Output is correct |
| 9 |
Correct |
114 ms |
98896 KB |
Output is correct |
| 10 |
Correct |
144 ms |
98920 KB |
Output is correct |
| 11 |
Correct |
94 ms |
99052 KB |
Output is correct |
| 12 |
Correct |
144 ms |
98920 KB |
Output is correct |
| 13 |
Correct |
165 ms |
169352 KB |
Output is correct |
| 14 |
Correct |
181 ms |
169292 KB |
Output is correct |
| 15 |
Correct |
292 ms |
169376 KB |
Output is correct |
| 16 |
Correct |
297 ms |
169364 KB |
Output is correct |
| 17 |
Incorrect |
196 ms |
169284 KB |
Output isn't correct |
| 18 |
Correct |
306 ms |
169260 KB |
Output is correct |
| 19 |
Correct |
293 ms |
169364 KB |
Output is correct |
| 20 |
Correct |
334 ms |
169388 KB |
Output is correct |
