제출 #1072947

#제출 시각아이디문제언어결과실행 시간메모리
1072947coolboy19521힘 센 거북 (IZhO11_turtle)C++17
10 / 100
2063 ms2568 KiB
// Thanks Benq #include "bits/stdc++.h" #define ll long long #define int ll using namespace std; const int sz = 1e6 + 6; const int sm = 22; vector<pair<int,int>> vp; vector<int> ps; int x[sz], y[sz]; 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) { 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 <= n; c *= p) e -= k / c; for (ll c = p; c <= n; 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; if (yds < 0) return 0; 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[k], 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...