Submission #868308

#	Time	Username	Problem	Language	Result	Execution time	Memory
868308		ND0322	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1727 ms	4180 KiB

amusementpark

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

const int MAXN = 18;
const int MOD = 998244353;


//if you find a dag that works reversing all edges creates a new dag
//ans would be edges * (#dag/2)
//the dags differ by their nodes

int n, m, popcount[1<<MAXN];

long long dp[1<<MAXN];

bool indep[1<<MAXN];

//dp = num dags using nodes in the mask
//indep is if a mask is an independant subset (no two nodes are connected)
//all submasks of independant submasks are independant as well
//for all independant subsets of mask:
//if(number of nodes in subset is odd) dp[mask] += dp[the rest of the mask]
//and because we overcount some
//if(number of nodes in subset is even) dp[mask] -= dp[the rest of the mask]



//every subset of an independant set is independant
//if it isnt then the whole thing isnt independant



int main(){
    
    scanf("%d %d", &n, &m);

    fill(indep, indep + (1<<n), 1);

    for(int i = 0; i < m; i++){
        int x,y; scanf("%d %d", &x, &y);

        indep[1<<(x-1) | 1<<(y-1)] = 0;
       
    }

    //same thing as the function
    for(int i = 0; i < n; i++){
        for(int j = (1<<n)-1; j >= 0; j--) if(j & (1<<i)) indep[j] &= indep[j ^ (1<<i)];
    }

    for(int i = 0; i < (1<<n); i++){
        popcount[i] = popcount[i>>1] + (i&1);
    }
    

    dp[0] = 1;

    for(int i = 0; i < (1<<n); i++){
        for(int j = i; j >= 1; j = (j-1) & i ){
            if(indep[j]){
                if(popcount[j] & 1) dp[i] = (dp[i] + dp[i^j]) % MOD;
                else dp[i] = (dp[i] - dp[i^j]) % MOD;
            }
        }
    }

    //https://math.stackexchange.com/questions/3361647/finding-inverse-of-2-mod-m
    int minv = ((1+MOD)/2);
    dp[(1 << n) - 1] = (dp[(1 << n) - 1] + MOD) % MOD;
    

    printf("%lld\n", dp[(1<<n)-1] * m % MOD * minv % MOD);

    

  


}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
amusementpark.cpp:42:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         int x,y; scanf("%d %d", &x, &y);
      |                  ~~~~~^~~~~~~~~~~~~~~~~

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