Submission #798304

#	Time	Username	Problem	Language	Result	Execution time	Memory
798304		Ronin13	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	2673 ms	2708 KiB

amusementpark

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <bitset>

#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back

using namespace std;

const ll mod = 998244353;
ll dp[(1 <<18)];
int main(){
    int n; cin >> n;
    int m; cin >> m;
    bool ind[(1 << n)];
    fill(ind, ind + (1 << n), 1);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        u--, v--;
        ind[(1 << u) | (1 << v)] = false;
    }
    for(int i = 1; i < (1 << n); i++){
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                ind[i] &= ind[i ^ (1 << j)];
            }
        }
    }
    dp[0] = 1;
    for(int i = 1; i < (1 << n); i++){
        int j = i;
        while(j){
            if(!ind[j]){
                j = (j - 1) & i;
                continue;
            }
            if(__builtin_popcount(j) & 1)
                dp[i] +=  dp[i ^ j];
            else dp[i] -=  dp[i ^ j];
            dp[i] %= mod; dp[i] += mod; dp[i] %= mod;
            j = (j - 1) & i;
        }
       // cout << dp[i] << "\n";
    }
    cout << (dp[(1 << n) - 1] * m)  % mod * ((mod + 1) / 2) % mod;
    return 0;
}

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