// Thanks Benq
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define ll long long
#define int ll
using namespace std;
const int sz = 6e5 + 2;
const int sm = 30;
vector<pair<int,int>> vp;
vector<int> ps;
ll wz[sm][sm];
ll dp[sm][sm];
bool sv[sz];
ll bpw(ll x, ll b, ll z) {
ll r = 1;
while (b) {
if (b & 1)
(r *= x) %= z;
(x *= x) %= z;
b >>= 1;
}
return r;
}
vector<pair<ll, ll>> factorize(ll z) {
vector<pair<ll, ll>> factors;
for (ll i = 2; i * i <= z; ++i) {
if (z % i == 0) {
ll count = 0;
while (z % i == 0) {
z /= i;
++count;
}
factors.push_back({i, count});
}
}
if (z > 1) {
factors.push_back({z, 1});
}
return factors;
}
ll chinese_remainder(vector<ll>& remainders, vector<ll>& moduli) {
ll result = 0, prod = 1;
for (auto m : moduli) prod *= m;
for (int i = 0; i < remainders.size(); i++) {
ll pp = prod / moduli[i];
result += remainders[i] * bpw(pp, moduli[i] - 2, moduli[i]) * pp;
result %= prod;
}
return result;
}
ll factorial_mod(ll n, ll p, ll pe) {
ll result = 1;
for (ll i = 1; i <= n; ++i) {
if (i % p != 0) {
result = (result * i) % pe;
}
}
return result;
}
ll nck_mod(ll n, ll k, ll p, ll e) {
if (k > n) return 0;
if (k == 0 || n == k) return 1;
ll pe = pow(p, e);
ll numerator = 1, denominator = 1;
while (n > 0 || k > 0) {
ll n_mod_p = n % p;
ll k_mod_p = k % p;
if (k_mod_p > n_mod_p) return 0;
numerator = (numerator * factorial_mod(n_mod_p, p, pe)) % pe;
denominator = (denominator * factorial_mod(k_mod_p, p, pe)) % pe;
denominator = (denominator * factorial_mod(n_mod_p - k_mod_p, p, pe)) % pe;
n /= p;
k /= p;
}
return (numerator * bpw(denominator, pe - pe/p - 1, pe)) % pe;
}
ll nck(ll n, ll k, ll z) {
if (n < k || n < 0) return 0;
if (k == 0 || n == k) return 1;
vector<pair<ll, ll>> factors = factorize(z);
vector<ll> remainders, moduli;
for (auto& factor : factors) {
ll p = factor.first;
ll e = factor.second;
ll pe = pow(p, e); // Compute p^e
moduli.push_back(pe);
remainders.push_back(nck_mod(n, k, p, e));
}
return chinese_remainder(remainders, moduli);
}
ll gt(pair<int,int>& f, pair<int,int>& s, int z) {
int xds = s.first - f.first;
int yds = s.second - f.second;
return nck(xds + yds, yds, z);
}
ll sb(ll a, ll b, ll z) {
return (a + z - b) % z;
}
ll ml(ll a, ll b, ll z) {
return a * b % z;
}
ll ad(ll a, ll b, ll z) {
return (a + b) % z;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll n, m, k, t, z;
cin >> n >> m >> k >> t >> z;
int sd = n + m + 2;
// int sd = sz;
for (ll i = 2; i < sd; i ++) {
if (sv[i]) continue;
ps.push_back(i);
sv[i] = true;
for (ll j = i * i; j < sd; j += i)
sv[j] = true;
}
for (int i = 0; i < k; i ++) {
int x, y;
cin >> x >> y;
vp.push_back(make_pair(x, y));
}
vp.push_back(make_pair(0, 0));
vp.push_back(make_pair(n, m));
sort(begin(vp), end(vp));
k = vp.size();
for (int i = 1; i < k; i ++) {
vector<int> an(k + 2);
for (int j = i - 1; 0 <= j; j --) {
wz[j][i] = an[j] = gt(vp[j], vp[i], z);
for (int l = j + 1; l < i; l ++)
wz[j][i] = sb(wz[j][i], ml(wz[j][l], an[l], z), z);
}
}
dp[0][1] = 1;
for (int i = 1; i < k; i ++)
for (int j = 0; j < i; j ++)
for (int l = 2; l <= t + 2; l ++)
dp[i][l] = ad(dp[i][l], ml(dp[j][l - 1], wz[j][i], z), z);
ll r = 0;
for (int i = 1; i <= t + 2; i ++)
r = ad(r, dp[k - 1][i], z);
// cout << ps.size() << '\n';
cout << r << '\n';
}
Compilation message
turtle.cpp: In function 'long long int chinese_remainder(std::vector<long long int>&, std::vector<long long int>&)':
turtle.cpp:51:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i = 0; i < remainders.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 9 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 10 |
Correct |
9 ms |
540 KB |
Output is correct |
| 11 |
Correct |
49 ms |
952 KB |
Output is correct |
| 12 |
Correct |
30 ms |
1504 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
1500 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
1504 KB |
Output isn't correct |
| 17 |
Incorrect |
2 ms |
1504 KB |
Output isn't correct |
| 18 |
Incorrect |
2 ms |
1504 KB |
Output isn't correct |
| 19 |
Incorrect |
2 ms |
1500 KB |
Output isn't correct |
| 20 |
Incorrect |
2 ms |
1504 KB |
Output isn't correct |
