#include<bits/stdc++.h>
using namespace std;
int TC = 0;
void dbg_out() {cout << endl;}
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {cout << " " << H; dbg_out(T...);}
#define debug(...) {cout << "(" << #__VA_ARGS__ << "):"; dbg_out(__VA_ARGS__);}
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define add push_back
#define size(v) (int) v.size()
#define left node * 2, l, (l + r) / 2
#define right node * 2 + 1, (l + r) / 2 + 1, r
#define check() cout << "Why doesn't this stupid a** code work?" << endl;
#define inf (int) 1e18
vector<int> dp(5000005, -1);
vector<int> x, y;
int n, m, k, t, z;
vector<int> f(300005, 0), f1(300005, 0);
long long pow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int C(int n, int k, int m){
return f[n] * f1[n - k] % m * f1[k] % m;
}
int find(int i){
if(dp[i] != -1){
return dp[i];
}
int X = 0, Y = 0;
for(int j = 0; j < 22; j++){
if(i & (1 << j)){
if(X > x[j]) dp[i] = 0;
if(Y > y[j]) dp[i] = 0;
X = x[j];
Y = y[j];
}
}
if(dp[i] != 0){
if(__builtin_popcount(i) == 2){
int l = -1, r = -1;
for(int j = 0; j < 22; j++){
if(i & (1 << j)){
if(l == -1) l = j;
r = j;
}
}
dp[i] = C(abs(x[l] - x[r]) + abs(y[l] - y[r]), abs(x[l] - x[r]), z);
int a = 0;
for(int j = l; j <= r; j++){
a += (1 << j);
}
for(int k = a; k; k = (k - 1) & a){
if(!(k & (1 << l)) || !(k & (1 << r)) || i == k) continue;
dp[i] -= find(k);
dp[i] = (dp[i] + z) % z;
}
}
else{
vector<int> ind;
for(int j = 0; j < 22; j++){
if(i & (1 << j)) ind.push_back(j);
}
int a = 0, b = 0;
for(int j = 0; j <= 1; j++) a += (1 << ind[j]);
for(int j = 1; j < size(ind); j++) b += (1 << ind[j]);
dp[i] = find(a) * find(b);
}
}
return dp[i];
}
void solve(){
cin >> n >> m >> k >> t >> z;
f[0] = f1[0] = 1;
for(int i = 1; i <= 300000; i++){
f[i] = f[i - 1] * i % z;
f1[i] = f1[i - 1] * pow(i, z - 2, z) % z;
}
vector<pair<int, int>> v = vector<pair<int,int>>(k + 2, {0, 0});
x = y = vector<int>(k + 2, 0);
for(int i = 1; i <= k; i++){
cin >> x[i] >> y[i];
v[i].first = x[i] + y[i];
v[i].second = i;
}
x[0] = y[0] = 0;
v[0].first = 0; v[0].second = 0;
x[k + 1] = n, y[k + 1] = m;
v[k + 1].first = n + m; v[k + 1].second = k + 1;
sort(all(v));
vector<int> a, b;
for(int i = 0; i <= k + 1; i++){
a.push_back(x[v[i].second]);
b.push_back(y[v[i].second]);
}
x = a, y = b;
for(int i = 0; i < (1 << (k + 2)); i++){
if(__builtin_popcount(i) < 2) continue;
dp[i] = find(i);
}
int ans = 0;
int a1 = 0;
for(int i = 0; i <= k + 1; i++){
a1 += (1 << i);
}
for(int e = a1; e; e = (e - 1) & a1){
if(__builtin_popcount(e) > t + 2 || !(e & 1) || !(e & (1 << (k + 1)))) continue;
ans = (ans + dp[e]) % z;
}
cout << ans << endl;
}
signed main(){
int q = 1;
//cin >> q;
while(++TC <= q){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
44124 KB |
Output is correct |
| 2 |
Incorrect |
130 ms |
44120 KB |
Output isn't correct |
| 3 |
Correct |
51 ms |
44260 KB |
Output is correct |
| 4 |
Incorrect |
82 ms |
44120 KB |
Output isn't correct |
| 5 |
Correct |
478 ms |
44256 KB |
Output is correct |
| 6 |
Incorrect |
71 ms |
44120 KB |
Output isn't correct |
| 7 |
Correct |
95 ms |
44124 KB |
Output is correct |
| 8 |
Correct |
70 ms |
44256 KB |
Output is correct |
| 9 |
Correct |
172 ms |
44120 KB |
Output is correct |
| 10 |
Incorrect |
270 ms |
44120 KB |
Output isn't correct |
| 11 |
Incorrect |
94 ms |
44120 KB |
Output isn't correct |
| 12 |
Incorrect |
278 ms |
44260 KB |
Output isn't correct |
| 13 |
Incorrect |
131 ms |
44120 KB |
Output isn't correct |
| 14 |
Incorrect |
295 ms |
44256 KB |
Output isn't correct |
| 15 |
Incorrect |
551 ms |
44264 KB |
Output isn't correct |
| 16 |
Incorrect |
541 ms |
44256 KB |
Output isn't correct |
| 17 |
Incorrect |
235 ms |
44368 KB |
Output isn't correct |
| 18 |
Incorrect |
1293 ms |
44272 KB |
Output isn't correct |
| 19 |
Incorrect |
1272 ms |
44368 KB |
Output isn't correct |
| 20 |
Incorrect |
548 ms |
44260 KB |
Output isn't correct |
