Submission #1262273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262273		euclid	Amusement Park (CEOI19_amusementpark)	C++20	100 / 100	1944 ms	2756 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vl vector<ll>

int n, m;
const int MN = 21, MS = (1<<18)+7, MOD = 998244353;
bool adj[MN][MN], f[MS]; //f[s]: whether s is an independent set
ll dp[MS]; //dp[s]: number of DAGs that can be formed by the points in s

int bits(int x) {return __builtin_popcount(x);}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u][v] = adj[v][u] = true; //ignore direction here
    }
    for(int i = 0; i < n; i++) dp[1<<i] = 1, f[1<<i] = true;
    for(int s = 1; s < 1<<n; s++) {
        if(bits(s)==1) continue;
        int lb = s&(-s), llb = (s^lb)&(-(s^lb));
        f[s] = f[s^lb] && f[s^llb] && !adj[(int)log2(lb)+1][(int)log2(llb)+1];
    }
    dp[0] = 1;
    for(int s = 1; s < 1<<n; s++) {
        if(bits(s)==1) continue;
        for(int ss = s; ss > 0; ss=(ss-1)&s) {
            if(!f[ss]) continue;
            ll d = dp[s^ss];
            if(bits(ss)%2==0) d *= -1;
            dp[s] = (dp[s]+d+MOD)%MOD;
        }
    }
    cout << dp[(1<<n)-1]*(MOD+1)/2%MOD*m%MOD << '\n';

}

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