Submission #154424

#TimeUsernameProblemLanguageResultExecution timeMemory
154424srvltEnergetic turtle (IZhO11_turtle)C++14
5 / 100
2083 ms600 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 = 700000; int n, m, k, t, z, ans, phi; 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 >>= 1LL; } return res; } int c(int a, int b) { if (a < 0) { return 0; } int res = 1; for (int i = 1; i <= a; i++) { res = res * (b - a + i) / i; res %= z; } return res; } 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; } } } phi = getphi(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 < (1LL << k); i++) { int sgn = 1; if (__builtin_popcountll(i) > t) { sgn = -1; } pii last = {0, 0}; int res = 1; bool wrong = false; for (int j = 0; j < k; j++) { if (i & (1LL << j)) { int dx = v[j].fi - last.fi + 1, dy = v[j].se - last.se + 1; if (v[j].fi < last.fi || v[j].se < last.se) { wrong = true; break; } int tmp = c(dx - 2, dx + dy - 3) + c(dx - 1, dx + dy - 3); 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...