Submission #90165

#TimeUsernameProblemLanguageResultExecution timeMemory
90165popovicirobertEnergetic turtle (IZhO11_turtle)C++14
5 / 100
316 ms3656 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long #define ld long double // 217 // 44 using namespace std; const int MAXN = (int) 3e5; const int MAXK = 50; bool ciur[2 * MAXN + 1]; vector <int> primes; int z; inline void mod(int &x) { if(x >= z) x -= z; } inline int lgput(int a, int b) { int ans = 1; while(b > 0) { if(b & 1) { ans = (1LL * ans * a) % z; } b >>= 1; a = (1LL * a * a) % z; } return ans; } inline void prec(int n) { int i, j; for(i = 2; i * i <= n; i++) { if(ciur[i] == 0) { for(j = i * i; j <= n; j += i) { ciur[j] = 1; } } } for(i = 2; i <= n; i++) { if(ciur[i] == 0) { primes.push_back(i); } } } int fr[2 * MAXN + 1]; inline void get(int n, int sign) { for(auto it : primes) { if(it > n) { break; } ll pw = it; while(pw <= n) { fr[it] += (n / pw) * sign; pw *= it; } } } inline int comb(int n, int k) { if(n < k) { return 0; } get(n, 1); get(k, -1); get(n - k, -1); int ans = 1; for(auto it : primes) { if(it > n) { break; } ans = (1LL * ans * lgput(it, fr[it])) % z; fr[it] = 0; } return ans; } struct Point { int x, y; bool operator <(const Point &other) const { if(x == other.x) { return y < other.y; } return x < other.x; } }; Point c[MAXK + 1]; int dp[MAXK + 1][MAXK + 1], ways[MAXK + 1][MAXK + 1]; int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, j, n, m, k, t; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> m >> k >> t >> z; prec(n + m); for(i = 1; i <= k; i++) { cin >> c[i].x >> c[i].y; } c[++k] = {0, 0}; c[++k] = {n, m}; sort(c + 1, c + k + 1); for(i = 1; i <= k; i++) { for(j = i; j <= k; j++) { ways[i][j] = comb(c[j].x - c[i].x + c[j].y - c[i].y, c[j].x - c[i].x); for(int p = i + 1; p < j; p++) { ways[i][j] -= (1LL * ways[i][p] * comb(c[p].x - c[i].x + c[p].y - c[i].y, c[p].x - c[i].x)) % z; ways[i][j] += z; mod(ways[i][j]); } } } dp[1][1] = 1; for(i = 2; i <= k; i++) { for(int nr = 1; nr <= min(k, t + 2); nr++) { for(j = i - 1; j >= 1; j--) { dp[i][nr] = (dp[i][nr] + 1LL * dp[j][nr - 1] * ways[j][i]) % z; } } } int ans = 0; for(i = 2; i <= t + 2; i++) { ans += dp[k][i]; mod(ans); } cout << ans; //cin.close(); //cout.close(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...