Submission #1095470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095470		gyg	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2370 ms	4952 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
const int MX_N = 18 + 2, MD = 998244353;

int n, m;
arr<arr<bool, MX_N>, MX_N> adj;

int md(int x) { return (x + MD) % MD; }
int expn(int x, int y) {
    if (y == 0) return 1;
    int ans = expn(x, y / 2);
    ans = md(ans * ans);
    if (y % 2 == 1) ans = md(ans * x);
    return ans;
}
int inv(int x) { return expn(x, MD - 2); }

arr<bool, 1 << MX_N> indp;
arr<int, 1 << MX_N> mltp;
void prcmp() {
    indp[0] = true;
    for (int msk = 1; msk < (1 << n); msk++) {
        for (int u = 1; u <= n; u++) {
            if (!(msk & (1 << (u - 1)))) continue;
            indp[msk] = indp[msk ^ (1 << (u - 1))];
            for (int v = 1; v <= n; v++) {
                if (!(msk & (1 << (v - 1)))) continue;
                if (v == u) continue;
                if (adj[u][v]) indp[msk] = false;
            }
            break;
        }
    }

    for (int msk = 0; msk < (1 << n); msk++) {
        int sz = 0;
        for (int u = 1; u <= n; u++) sz += (bool) (msk & (1 << (u - 1)));
        mltp[msk] = (sz % 2 == 1) ? 1 : md(-1);
    }
}

arr<int, 1 << MX_N> dp;
void cmp() {
    dp[0] = 1;
    for (int msk = 1; msk < (1 << n); msk++) 
        for (int sb_msk = msk; sb_msk != 0; sb_msk = (sb_msk - 1) & msk) 
            if (indp[sb_msk]) dp[msk] = md(dp[msk] + md(mltp[sb_msk] * dp[msk ^ sb_msk]));        
}

signed main() {
    // freopen("prk.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u][v] = adj[v][u] = true;
    }
    
    prcmp();
    cmp();
    
    int ans = md(md(dp[(1 << n) - 1] * m) * inv(2));
    cout << ans << endl;
}

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