#include<bits/stdc++.h>
using namespace::std;
const int MAX = 600000 + 5;
const int N = 23;
int n;
int m;
int k;
int t;
int z;
int f[MAX];
int fi[MAX];
int pot[MAX];
int memo[N][N];
vector<pair<int, int>> v;
inline int mul(int a, int b, int MOD){
return (1ll * a * b) % MOD;
}
int pow_mod(int a, int b, int MOD){
int r = 1 % MOD;
while(b){
if(b & 1) r = mul(r, a, MOD);
a = mul(a, a, MOD);
b >>= 1;
}
return r;
}
void init(int p, int e, int mod){
f[0] = 1;
pot[0] = 0;
for(int i = 1; i < MAX; i++){
int x = i;
pot[i] = pot[i - 1];
while(x % p == 0){
pot[i]++;
x /= p;
}
f[i] = mul(x, f[i - 1], mod);
}
fi[MAX - 1] = pow_mod(f[MAX - 1], mod - mod / p - 1, mod);
for(int i = MAX - 2; i >= 0; i--){
int x = i + 1;
while(x % p == 0) x /= p;
fi[i] = mul(x, fi[i + 1], mod);
}
}
int C(int a, int b, int p, int e, int mod){
if(a < b) return 0;
if(pot[a] - pot[b] - pot[a - b] >= e) return 0;
return mul(pow_mod(p, pot[a] - pot[b] - pot[a - b], mod), mul(f[a], mul(fi[b], fi[a - b], mod), mod), mod);
}
void preprocess(int p, int e, int mod){
for(int i = 0; i < v.size(); i++){
for(int j = i; j < v.size(); j++){
if(v[i].second > v[j].second) continue;
int dx = v[j].first - v[i].first;
int dy = v[j].second - v[i].second;
memo[i][j] = C(dx + dy, dx, p, e, mod);
for(int k = i + 1; k < j; k++){
if(v[i].second > v[k].second or v[k].second > v[j].second) continue;
memo[i][j] += mod - mul(memo[i][k], C(v[j].first - v[k].first + v[j].second - v[k].second, v[j].first - v[k].first, p, e, mod), mod);
if(memo[i][j] >= mod) memo[i][j] -= mod;
}
}
}
}
typedef long long ll;
ll euclid(ll a, ll b, ll &x, ll &y) {
if (b) { ll d = euclid(b, a % b, y, x);
return y -= a/b * x, d; }
return x = 1, y = 0, a;
}
ll crt(ll a, ll m, ll b, ll n) {
if (n > m) swap(a, b), swap(m, n);
ll x, y, g = euclid(m, n, x, y);
assert((a - b) % g == 0); // else no solution
x = (b - a) % n * x % n / g * m + a;
return x < 0 ? x + m*n/g : x;
}
ll crt(vector<pair<int, int>> &v){
while(v.size() > 1){
pair<int, int> p1 = v.back(); v.pop_back();
pair<int, int> p2 = v.back(); v.pop_back();
int m = crt(p1.first, p1.second, p2.first, p2.second);
v.emplace_back(make_pair(m, p1.second * p2.second));
}
return v.back().first;
}
int compute(int p, int e, int mod){
init(p, e, mod);
preprocess(p, e, mod);
int ans = 0;
for(int mask = 0; mask < (1 << k); mask++){
if(__builtin_popcount(mask) > t) continue;
int last = 0;
int res = 1;
for(int i = 0, p = 1; i < k; i++, p <<= 1){
if(mask & p){
res = mul(res, memo[last][i + 1], mod);
last = i + 1;
}
}
res = mul(res, memo[last][v.size() - 1], mod);
ans += res;
if(ans >= mod) ans -= mod;
}
return ans;
}
int solve(){
if(z == 1) return 0;
vector<pair<int, int>> mods;
for(int i = 2; i * i <= z; i++){
if(z % i == 0){
int p = i;
int e = 0;
int val = 1;
while(z % i == 0){
val *= i;
z /= i;
e++;
}
mods.emplace_back(make_pair(compute(p, e, val), val));
}
}
if(z > 1){
mods.emplace_back(make_pair(compute(z, 1, z), z));
}
return crt(mods);
}
int main(){
scanf("%d %d %d %d %d", &n, &m, &k, &t, &z);
v.emplace_back(make_pair(0, 0));
for(int i = 0; i < k; i++){
int x, y;
scanf("%d %d", &x, &y);
v.emplace_back(make_pair(x, y));
}
v.emplace_back(make_pair(n, m));
sort(v.begin(), v.end());
printf("%d\n", solve());
return 0;
}
Compilation message
turtle.cpp: In function 'void preprocess(int, int, int)':
turtle.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
turtle.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int j = i; j < v.size(); j++){
| ~~^~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | scanf("%d %d %d %d %d", &n, &m, &k, &t, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
7332 KB |
Output is correct |
| 2 |
Correct |
69 ms |
7320 KB |
Output is correct |
| 3 |
Correct |
22 ms |
7244 KB |
Output is correct |
| 4 |
Correct |
25 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
118 ms |
7332 KB |
Output is correct |
| 6 |
Correct |
22 ms |
7344 KB |
Output is correct |
| 7 |
Correct |
26 ms |
7228 KB |
Output is correct |
| 8 |
Correct |
21 ms |
7256 KB |
Output is correct |
| 9 |
Correct |
29 ms |
7336 KB |
Output is correct |
| 10 |
Correct |
36 ms |
7244 KB |
Output is correct |
| 11 |
Correct |
25 ms |
7252 KB |
Output is correct |
| 12 |
Correct |
59 ms |
7336 KB |
Output is correct |
| 13 |
Correct |
70 ms |
7244 KB |
Output is correct |
| 14 |
Correct |
88 ms |
7336 KB |
Output is correct |
| 15 |
Correct |
256 ms |
7232 KB |
Output is correct |
| 16 |
Correct |
79 ms |
7296 KB |
Output is correct |
| 17 |
Correct |
75 ms |
7336 KB |
Output is correct |
| 18 |
Correct |
80 ms |
7332 KB |
Output is correct |
| 19 |
Correct |
119 ms |
7340 KB |
Output is correct |
| 20 |
Correct |
266 ms |
7340 KB |
Output is correct |
