Submission #844836

#TimeUsernameProblemLanguageResultExecution timeMemory
844836AndriaBeridzeEnergetic turtle (IZhO11_turtle)C++14
50 / 100
1272 ms44380 KiB
#include<bits/stdc++.h> using namespace std; int TC = 0; void dbg_out() {cout << endl;} template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {cout << " " << H; dbg_out(T...);} #define debug(...) {cout << "(" << #__VA_ARGS__ << "):"; dbg_out(__VA_ARGS__);} #define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define int long long #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define add push_back #define size(v) (int) v.size() #define left node * 2, l, (l + r) / 2 #define right node * 2 + 1, (l + r) / 2 + 1, r #define check() cout << "Why doesn't this stupid a** code work?" << endl; #define inf (int) 1e18 vector<int> dp(5000005, -1); vector<int> x, y; int n, m, k, t, z; vector<int> f(300005, 0), f1(300005, 0); long long pow(long long a, long long b, long long m) { a %= m; long long res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } int C(int n, int k, int m){ return f[n] * f1[n - k] % m * f1[k] % m; } int find(int i){ if(dp[i] != -1){ return dp[i]; } int X = 0, Y = 0; for(int j = 0; j < 22; j++){ if(i & (1 << j)){ if(X > x[j]) dp[i] = 0; if(Y > y[j]) dp[i] = 0; X = x[j]; Y = y[j]; } } if(dp[i] != 0){ if(__builtin_popcount(i) == 2){ int l = -1, r = -1; for(int j = 0; j < 22; j++){ if(i & (1 << j)){ if(l == -1) l = j; r = j; } } dp[i] = C(abs(x[l] - x[r]) + abs(y[l] - y[r]), abs(x[l] - x[r]), z); int a = 0; for(int j = l; j <= r; j++){ a += (1 << j); } for(int k = a; k; k = (k - 1) & a){ if(!(k & (1 << l)) || !(k & (1 << r)) || i == k) continue; dp[i] -= find(k); dp[i] = (dp[i] + z) % z; } } else{ vector<int> ind; for(int j = 0; j < 22; j++){ if(i & (1 << j)) ind.push_back(j); } int a = 0, b = 0; for(int j = 0; j <= 1; j++) a += (1 << ind[j]); for(int j = 1; j < size(ind); j++) b += (1 << ind[j]); dp[i] = find(a) * find(b) % z; } } return dp[i]; } void solve(){ cin >> n >> m >> k >> t >> z; f[0] = f1[0] = 1; for(int i = 1; i <= 300000; i++){ f[i] = f[i - 1] * i % z; f1[i] = f1[i - 1] * pow(i, z - 2, z) % z; } vector<pair<int, int>> v = vector<pair<int,int>>(k + 2, {0, 0}); x = y = vector<int>(k + 2, 0); for(int i = 1; i <= k; i++){ cin >> x[i] >> y[i]; v[i].first = x[i] + y[i]; v[i].second = i; } x[0] = y[0] = 0; v[0].first = 0; v[0].second = 0; x[k + 1] = n, y[k + 1] = m; v[k + 1].first = n + m; v[k + 1].second = k + 1; sort(all(v)); vector<int> a, b; for(int i = 0; i <= k + 1; i++){ a.push_back(x[v[i].second]); b.push_back(y[v[i].second]); } x = a, y = b; for(int i = 0; i < (1 << (k + 2)); i++){ if(__builtin_popcount(i) < 2) continue; dp[i] = find(i); } int ans = 0; int a1 = 0; for(int i = 0; i <= k + 1; i++){ a1 += (1 << i); } for(int e = a1; e; e = (e - 1) & a1){ if(__builtin_popcount(e) > t + 2 || !(e & 1) || !(e & (1 << (k + 1)))) continue; ans = (ans + dp[e]) % z; } cout << ans << endl; } signed main(){ int q = 1; //cin >> q; while(++TC <= q){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...