Submission #787050

#	Time	Username	Problem	Language	Result	Execution time	Memory
787050		nonono	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	1624 ms	2880 KiB

amusementpark

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

const int mod = 998244353;

int n, m;
bool f[1 << 18];
int dp[1 << 18];

int binpow(int a, int b) {
    if(!b) return 1;
    
    if(b % 2 == 0) {
        int x = binpow(a, b / 2);
        return (x * x) % mod;
    }
    
    return (binpow(a, b - 1) * a) % mod;
}

signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    for(int mask = 0; mask < (1 << n); mask ++) f[mask] = false; 
    
    for(int i = 1; i <= m; i ++) {
        int u, v;
        cin >> u >> v;
        u -- ; v -- ;
        f[(1 << u) + (1 << v)] = true;
    } 
    
    for(int mask = 1; mask < (1 << n); mask ++) {
        for(int i = 0; i < n; i ++) {
            if((mask & (1 << i)) && f[mask ^ (1 << i)]) {
                f[mask] = true;
            }
        }
    }
    
    dp[0] = 1;
    for(int mask = 1; mask < (1 << n); mask ++) {
        for(int i = mask; i > 0; i = (i - 1) & mask) {
            if(f[i]) continue ;
            
            if(__builtin_popcount(i) % 2) dp[mask] += dp[mask ^ i];
            else 
                dp[mask] += mod - dp[mask ^ i];
            
            dp[mask] %= mod;    
        }
    }
    
    cout << dp[(1 << n) - 1] * m % mod * binpow(2, mod - 2) % mod << "\n"; 
    return 0;
}

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