Submission #683417

#TimeUsernameProblemLanguageResultExecution timeMemory
683417nifesheEnergetic turtle (IZhO11_turtle)C++17
0 / 100
2088 ms24116 KiB
#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; } } r[x]++; 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++) { if(__builtin_popcount(mask) > t) continue; int sign = (__builtin_popcount(mask) & 1? -1 : 1); add(ans, sign * 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...