Submission #1177577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177577		vjudge2	Amusement Park (CEOI19_amusementpark)	C++20	100 / 100	2021 ms	4800 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 998244353;

const int N = 1 << 18;
int dp[N], conn[18][18], sb[N];
bool indep[N];

int bm(int b, int p) {
    if (!p) return 1;
    int res = bm(b, p / 2);
    res = res * res % mod;
    if (p % 2 == 1) res = res * b % mod;
    return res;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        conn[u][v] = 1;
    }
    for (int i = 0; i < (1 << n); i++) {
        indep[i] = 1;
        for (int j = 0; j < n; j++) if ((1 << j) & i) sb[i]++;
        sb[i]++;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if ((i & (1 << j)) && (i & (1 << k)) && conn[j][k]) {
                    indep[i] = 0;
                    break;
                }
            }
            if (!indep[i]) break;
        }
    }
    dp[0] = 1;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = i; j; j = (j - 1) & i) {
            if (indep[j]) (dp[i] += (dp[i ^ j] * ((sb[j] % 2 == 1) ? mod-1 : 1)) % mod) %= mod;
        }
    }
    cout << dp[(1 << n) - 1] * m % mod * bm(2, mod-2) % mod << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37