Submission #1307158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307158		Nipphitch	Amusement Park (CEOI19_amusementpark)	C++20	100 / 100	1805 ms	6888 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=18;
const int mod=998244353;

int n,m,adj[N+1],popcou[(1<<N)+1],ar[(1<<N)+1],id[(1<<N)+1],dp[(1<<N)+1],ans;
bool inde[(1<<N)+1];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        u--,v--;
        adj[u]|=(1<<v);
        adj[v]|=(1<<u);
    }
    for(int i=0;i<n;i++) id[(1<<i)]=i;
    for(int mask=0;mask<(1<<n);mask++){
        popcou[mask]=__builtin_popcount(mask);
        if(popcou[mask]%2==1) ar[mask]=1;
        else ar[mask]=-1;
    }
    inde[0]=true;
    for(int mask=1;mask<(1<<n);mask++){
        if(inde[mask&(mask-1)] && !(adj[id[mask&(-mask)]]&(mask&(mask-1)))){
            inde[mask]=true;
        }
    }
    dp[0]=1;
    for(int mask=1;mask<(1<<n);mask++){
        for(int sub=mask;sub;sub=(sub-1)&mask){
            if(inde[sub]){
                dp[mask]=(dp[mask]+ar[sub]*dp[mask^sub])%mod;
            }
        }
    }
    ans=dp[(1<<n)-1];
    if(ans<0) ans+=mod;
    ans=(ans*m)%mod;
    ans=(ans*(mod+1)/2)%mod;
    cout << ans;
}

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