#include "bits/stdc++.h"
using namespace std;
int mod;
int C[5000][5000];
int choose(int n, int k) {
if (k > n || k < 0) {
return 0;
}
return C[n][k];
}
void solve() {
int n, m, k, t;
cin >> n >> m >> k >> t >> mod;
for (int i = 0; i < 5000; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
C[i][j] = 1 % mod;
} else {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
}
t += 2;
vector<pair<int, int>> a = {{0, 0}, {n, m}};
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
a.push_back({x, y});
}
std::sort(a.begin(), a.end());
const int N = (int) a.size();
vector<int> dp(1 << N);
vector<vector<int>> cnt(N, vector<int> (N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (a[i].first <= a[j].first && a[i].second <= a[j].second) {
cnt[i][j] = choose(a[j].first + a[j].second - a[i].first - a[i].second, a[j].first - a[i].first);
}
}
}
vector<int> calc(1 << N);
for (int msk = 0; msk < (1 << N); msk++) {
int c = 1 % mod, prev = -1;
for (int i = 0; i < N; i++) {
if (msk >> i & 1) {
if (prev != -1) {
c = c * 1ll * cnt[prev][i] % mod;
}
prev = i;
}
}
calc[msk] = c;
}
vector<int> path(N + 1);
vector<vector<int>> mem(N + 1);
for (int msk = 0; msk < (1 << N); msk++) {
if (msk >> (N - 1) & 1) {
if (msk & 1) {
if (calc[msk]) {
mem[__builtin_popcount(msk)].push_back(msk);
}
}
}
}
for (int i = N; i >= 2; i--) {
for (auto msk : mem[i]) {
(path[i] += calc[msk]) %= mod;
}
for (int j = i + 1; j <= N; j++) {
int val = choose(j - 2, i - 2) * 1ll * path[j] % mod;
if (j % 2 != i % 2 || 1) {
(path[i] += mod - val) %= mod;
} else {
(path[i] += val) %= mod;
}
}
// cout << path[i] << endl;
}
vector<vector<int>> DP(N, vector<int> (t + 1));
DP[0][1] = 1;
for (int i = 1; i < N; i++) {
for (int j = 2; j <= t; j++) {
for (int pr = 0; pr < i; pr++) {
(DP[i][j] += DP[pr][j - 1] * 1ll * cnt[pr][i] % mod) %= mod;
}
for (int pr = 0; pr < i; pr++) {
(DP[i][j] += mod - DP[pr][j] * 1ll * cnt[pr][i] % mod) %= mod;
}
}
}
int ans = 0;
for (int i = 0; i <= min(N, t); i++) {
(ans += DP[N - 1][i]) %= mod;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
36 ms |
97924 KB |
Output is correct |
| 2 |
Correct |
36 ms |
98120 KB |
Output is correct |
| 3 |
Correct |
37 ms |
98136 KB |
Output is correct |
| 4 |
Correct |
44 ms |
99144 KB |
Output is correct |
| 5 |
Correct |
310 ms |
130900 KB |
Output is correct |
| 6 |
Correct |
40 ms |
98120 KB |
Output is correct |
| 7 |
Correct |
56 ms |
100004 KB |
Output is correct |
| 8 |
Correct |
42 ms |
98120 KB |
Output is correct |
| 9 |
Runtime error |
171 ms |
206920 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
194 ms |
215364 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
168 ms |
200748 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
194 ms |
214364 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
175 ms |
197720 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
194 ms |
200792 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
224 ms |
230288 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
218 ms |
231536 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
197 ms |
206932 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
221 ms |
231252 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
234 ms |
229720 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
213 ms |
231264 KB |
Execution killed with signal 11 |
