# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1062580 | sleepntsheep | Amusement Park (CEOI19_amusementpark) | C++17 | 0 ms | 348 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
const ll M = 998244353;
vector<int> g[22];
int n, m, a[999], b[999], p[22], q[22];
ii dp[1<<22];
ll bpow(ll a, ll b) {
if (!b) return 1;
ll r = bpow(a, b / 2);
if (b & 1) return r * r % M * a % M;
return r * r % M;
}
ii add(ii a, ii b) {
return {(a.first * 1ll * a.second % M + b.first * 1ll * b.second % M) % M * 1ll * bpow((a.second + b.second) % M, M - 2) % M
, (a.second + b.second) % M};
}
ii prod(ii a, ll b) {
return {(a.first * 1ll * a.second % M + b * a.second % M) % M * 1ll * bpow(a.second, M - 2) % M,
a.second};
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
scanf("%d%d", a+i, b+i), --a[i], --b[i], g[b[i]].push_back(a[i]);
dp[0] = {0, 1};
for (int j = 0; j < (1 << n); ++j) {
for (int i = 0; i < n; ++i) if (j & (1 << i)) {
int k = j & ~(1 << i), c {};
for (int v : g[i]) c += (k >> v) & 1;
dp[j] = add(dp[j], prod(dp[k], c));
}
}
printf("%lld", dp[(1 << n) - 1].first * 1ll * dp[(1 << n) - 1].second % M);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |