Submission #1279638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279638		not_amir	Amusement Park (CEOI19_amusementpark)	C++20	100 / 100	1820 ms	1496 KiB

amusementpark

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

typedef long long ll;

constexpr int MOD = 998'244'353;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> G(n, vector<bool>(n));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u - 1][v - 1] = G[v - 1][u - 1] = true;
    }
    vector<bool> independent(1 << n);
    independent[0] = true;
    for (int i = 1; i < 1 << n; i++) {
        int v = -1;
        for (int j = 0; v == -1 && j < n; j++)
            if (i >> j & 1) v = j;
        independent[i] = independent[i ^ 1 << v];
        for (int j = v + 1; j < n; j++)
            if (i >> j & 1 && G[v][j])
                independent[i] = false;
    }
    vector<int> dp(1 << n);
    dp[0] = 1;
    for (int i = 1; i < 1 << n; i++)
        for (int j = i; j; j = j - 1 & i)
            if (independent[j])
                dp[i] = (dp[i] + 1ll * (__builtin_popcount(j) % 2 ? 1 : MOD - 1) * dp[i ^ j]) % MOD;
    cout << (1ll * dp[(1 << n) - 1] * m % MOD * ((MOD + 1) / 2) % MOD);
}

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