Submission #154408

#TimeUsernameProblemLanguageResultExecution timeMemory
154408srvltEnergetic turtle (IZhO11_turtle)C++14
5 / 100
1119 ms9936 KiB
//#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define ll long long #define db long double #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define fi first #define se second #define mp make_pair #define endl "\n" #define int long long using namespace std; void dout() { cerr << endl; } template <typename Head, typename... Tail> void dout(Head H, Tail... T) { cerr << H << ' '; dout(T...); } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef pair <int, int> pii; const int M = 600000; int n, m, k, t, z, ans, f[M + 3], fr[M + 3]; vector <pii> v; vector <bool> prime(M + 3, true); int binpow(int x, int y) { int res = 1; while (y > 0) { if (y & 1) { res = res * x % z; } x = x * x % z; y >>= 1; } return res; } int c(int a, int b) { return (f[b] * fr[a] % z) * fr[b - a] % z; } int getphi(int x) { if (x == 1) { return 1; } for (int i = 2; i * i <= x; i++) { if (prime[i] && x % i == 0) { int tmp = 1; while (x > 1 && x % i == 0) { tmp *= i; x /= i; } tmp /= i; return getphi(x) * tmp * (i - 1) % z; } } return (x - 1) % z; } void solve(int tc) { cin >> n >> m >> k >> t >> z; prime[0] = prime[1] = false; for (int i = 2; i <= M; i++) { if (prime[i]) { for (int j = i * i; j <= M; j += i) { prime[j] = false; } } } int phi = getphi(z); f[0] = fr[0] = 1; for (int i = 1; i <= M; i++) { f[i] = f[i - 1] * i % z; fr[i] = fr[i - 1] * binpow(i, phi - 1) % z; } for (int i = 0; i < k; i++) { pii p; cin >> p.fi >> p.se; v.pb(p); } sort(v.begin(), v.end()); for (int i = 0; i < (1 << k); i++) { int sgn = 1; if (__builtin_popcount(i) > t) { sgn = -1; } pii last = {0, 0}; int res = 1; bool wrong = false; for (int j = 0; j < k; j++) { if (i & (1 << j)) { int dx = v[j].fi - last.fi + 1, dy = v[j].se - last.se + 1; if (dy < 1) { wrong = true; break; } int tmp = c(dx - 1, dx + dy - 2); res = res * tmp % z; last = v[j]; } } if (wrong) { continue; } int dx = n - last.fi + 1, dy = m - last.se + 1; int tmp = c(dx - 1, dx + dy - 2); res = res * tmp % z; ans = (ans + res * sgn + z) % z; } cout << ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int tc = 1; // cin >> tc; for (int i = 0; i < tc; i++) { solve(i); // cleanup(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...