Submission #1073029

#TimeUsernameProblemLanguageResultExecution timeMemory
1073029coolboy19521Energetic turtle (IZhO11_turtle)C++17
25 / 100
2086 ms1620 KiB
// Thanks Benq #include "bits/stdc++.h" #define ll long long #define int ll using namespace std; const int sz = 6e5 + 2; const int sm = 30; vector<pair<int,int>> vp; vector<int> ps; ll wz[sm][sm]; ll dp[sm][sm]; bool sv[sz]; ll bpw(ll x, ll b, ll z) { ll r = 1; while (b) { if (b & 1) (r *= x) %= z; (x *= x) %= z; b >>= 1; } return r; } ll nck(ll n, ll k, ll z) { if (n < k || n < 0) return 0; if (k == 0 || n == k) return 1; if (k == 1 || k == n - 1) return n; ll r = 1; for (ll i = 0; i < (ll) ps.size(); i ++) { ll p = ps[i], e = 0; if (p > n) break; for (ll c = p; c <= n; c *= p) e += n / c; for (ll c = p; c <= k; c *= p) e -= k / c; for (ll c = p; c <= (n - k); c *= p) e -= (n - k) / c; (r *= bpw(p, e, z)) %= z; } return r; } ll gt(pair<int,int> f, pair<int,int> s, int z) { int xds = s.first - f.first; int yds = s.second - f.second; return nck(xds + yds, yds, z); } ll sb(ll a, ll b, ll z) { return (a + z - b) % z; } ll ml(ll a, ll b, ll z) { return a * b % z; } ll ad(ll a, ll b, ll z) { return (a + b) % z; } signed main() { for (ll i = 2; i < sz; i ++) { if (sv[i]) continue; ps.push_back(i); sv[i] = true; for (ll j = i * i; j < sz; j += i) sv[j] = true; } ll n, m, k, t, z; cin >> n >> m >> k >> t >> z; for (int i = 0; i < k; i ++) { int x, y; cin >> x >> y; vp.push_back(make_pair(x, y)); } vp.push_back(make_pair(0, 0)); vp.push_back(make_pair(n, m)); sort(begin(vp), end(vp)); k = vp.size(); for (int i = 1; i < k; i ++) for (int j = i - 1; 0 <= j; j --) { wz[j][i] = gt(vp[j], vp[i], z); for (int l = j + 1; l < i; l ++) wz[j][i] = sb(wz[j][i], ml(wz[j][l], gt(vp[l], vp[i], z), z), z); } dp[0][0] = 1; for (int i = 1; i < k; i ++) for (int j = 0; j < i; j ++) for (int l = 1; l <= t + 1; l ++) dp[i][l] = ad(dp[i][l], ml(dp[j][l - 1], wz[j][i], z), z); ll r = 0; for (int i = 1; i <= t + 1; i ++) r = ad(r, dp[k - 1][i], z); cout << r << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...