#include <bits/stdc++.h>
#define int long long
#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){
if(b == 0) return 1;
return pm(a * a % Z, b / 2, Z) * (b % 2 ? a : 1) % Z;
}
int mi(int a, int Z){
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[22][2], d[22][22];
int Cu[22];
int32_t main(){
int 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++){
int 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);
if(U >= T + 1){
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 << ((s - t) % Z + Z) % Z << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
141084 KB |
Output is correct |
| 2 |
Incorrect |
151 ms |
141132 KB |
Output isn't correct |
| 3 |
Correct |
84 ms |
102600 KB |
Output is correct |
| 4 |
Correct |
68 ms |
84780 KB |
Output is correct |
| 5 |
Correct |
88 ms |
102644 KB |
Output is correct |
| 6 |
Incorrect |
90 ms |
84896 KB |
Output isn't correct |
| 7 |
Correct |
84 ms |
84848 KB |
Output is correct |
| 8 |
Correct |
70 ms |
84772 KB |
Output is correct |
| 9 |
Correct |
79 ms |
84788 KB |
Output is correct |
| 10 |
Correct |
93 ms |
84836 KB |
Output is correct |
| 11 |
Correct |
69 ms |
84940 KB |
Output is correct |
| 12 |
Correct |
77 ms |
84776 KB |
Output is correct |
| 13 |
Correct |
148 ms |
141164 KB |
Output is correct |
| 14 |
Correct |
148 ms |
141072 KB |
Output is correct |
| 15 |
Correct |
158 ms |
141088 KB |
Output is correct |
| 16 |
Correct |
219 ms |
141192 KB |
Output is correct |
| 17 |
Incorrect |
167 ms |
141136 KB |
Output isn't correct |
| 18 |
Correct |
232 ms |
141180 KB |
Output is correct |
| 19 |
Correct |
215 ms |
141104 KB |
Output is correct |
| 20 |
Correct |
157 ms |
141184 KB |
Output is correct |
