#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 16777216")
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long
using namespace std;
using namespace __gnu_pbds;
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 1e6;
const int lg = 20;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);
int binpow(int x, int n) {
int ans = 1;
while(n) {
if(n & 1) ans = (ans * x) % mod;
n /= 2;
x = (x * x) % mod;
}
return ans;
}
void add(int &a, int b) {
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
}
vector<int> primes;
int phi = 1;
int fact[MAX], inv[MAX];
void precalc() {
map<int, int> r;
int x = mod;
for(int i = 2; i * i <= x; i++) {
while(x % i == 0) {
r[i]++;
x /= i;
}
}
for(auto [p, cnt] : r) {
phi *= binpow(p, cnt) - binpow(p, cnt - 1);
primes.pb(p);
}
fact[0] = inv[0] = fact[1] = inv[1] = 1;
for(int i = 2; i < MAX; i++) {
int x = i;
for(auto p : primes) {
while(x % p == 0) x /= p;
}
fact[i] = (fact[i - 1] * x) % mod;
inv[i] = binpow(fact[i], phi - 1);
}
}
int C(int n, int k) {
auto get = [&](int x, int p) {
int ans = 0;
int pw = p;
while(pw <= x) {
ans += x / pw;
pw *= p;
}
return ans;
};
int ans = fact[n] * inv[k] % mod * inv[n - k] % mod;
for(auto p : primes) {
int cnt = get(n, p) - get(k, p) - get(n - k, p);
ans = (ans * binpow(p, cnt)) % mod;
}
// cout << n << " choose " << k << " = " << ans << endl;
return ans;
}
void solve() {
int n, m, k, t;
cin >> n >> m >> k >> t >> mod; precalc();
vector<pair<int, int>> a(k);
for(auto &[x, y] : a) {
cin >> x >> y;
}
sort(all(a));
int ans = 0;
vector<int> ways((1 << k));
for(int mask = 0; mask < (1 << k); mask++) {
vector<pair<int, int>> need = {{0, 0}};
for(int i = 0; i < k; i++) {
if(mask >> i & 1) {
need.pb(a[i]);
}
}
need.pb({n, m});
int sz = sz(need);
int add = 1;
for(int i = 1; i < sz; i++) {
if(need[i - 1].s > need[i].s) {
add = 0;
break;
}
int x = need[i].f - need[i - 1].f, y = need[i].s - need[i - 1].s;
add = (add * C(x + y, y)) % mod;
}
int sign = (__builtin_popcount(mask) & 1? -1 : 1);
ways[mask] = sign * add;
}
for(int i = 0; i < k; i++) {
for(int mask = 0; mask < (1 << k); mask++) {
if(mask >> i & 1) continue;
add(ways[mask], ways[mask | (1 << i)]);
}
}
for(int mask = 0; mask < (1 << k); mask++) {
int sign = (__builtin_popcount(mask) & 1? -1 : 1);
ways[mask] *= sign;
}
for(int mask = 0; mask < (1 << k); mask++) {
if(__builtin_popcount(mask) > t) continue;
int sign = (__builtin_popcount(mask) & 1? -1 : 1);
add(ans, ways[mask]);
}
cout << ans << '\n';
}
signed main() {
// freopen("turtle.in", "r", stdin); freopen("turtle.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ttt = 1;
// cin >> ttt;
while(ttt--) {
solve();
}
return 0;
}
Compilation message
turtle.cpp: In function 'void solve()':
turtle.cpp:145:13: warning: unused variable 'sign' [-Wunused-variable]
145 | int sign = (__builtin_popcount(mask) & 1? -1 : 1);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
15992 KB |
Output is correct |
| 2 |
Correct |
502 ms |
15928 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
15880 KB |
Output isn't correct |
| 4 |
Incorrect |
24 ms |
16184 KB |
Output isn't correct |
| 5 |
Incorrect |
263 ms |
24072 KB |
Output isn't correct |
| 6 |
Incorrect |
16 ms |
15900 KB |
Output isn't correct |
| 7 |
Incorrect |
28 ms |
16468 KB |
Output isn't correct |
| 8 |
Incorrect |
15 ms |
15884 KB |
Output isn't correct |
| 9 |
Incorrect |
71 ms |
18004 KB |
Output isn't correct |
| 10 |
Incorrect |
148 ms |
19976 KB |
Output isn't correct |
| 11 |
Incorrect |
29 ms |
16468 KB |
Output isn't correct |
| 12 |
Incorrect |
145 ms |
19984 KB |
Output isn't correct |
| 13 |
Correct |
498 ms |
15904 KB |
Output is correct |
| 14 |
Correct |
954 ms |
17056 KB |
Output is correct |
| 15 |
Correct |
1362 ms |
24100 KB |
Output is correct |
| 16 |
Correct |
1352 ms |
24112 KB |
Output is correct |
| 17 |
Correct |
714 ms |
18032 KB |
Output is correct |
| 18 |
Execution timed out |
2086 ms |
24184 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2073 ms |
24176 KB |
Time limit exceeded |
| 20 |
Correct |
1254 ms |
24156 KB |
Output is correct |
