Submission #1011147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011147		Oz121	Amusement Park (CEOI19_amusementpark)	Java	63 / 100	3068 ms	31760 KiB

amusementpark

import java.io.*;
import java.util.*;
public class amusementpark {
    public static int mod = 998244353;
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine());
        int num = Integer.parseInt(l1.nextToken()); int m = Integer.parseInt(l1.nextToken());

        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (int i = 0;i<num;i++) graph.put(i,new ArrayList<>());

        for (int i = 0;i<m;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            int a = Integer.parseInt(st.nextToken())-1; int b = Integer.parseInt(st.nextToken())-1;
            graph.get(a).add(b);
        }

        //Store if a set i of vertices is independent or not
        ArrayList<Integer> indep = new ArrayList<>();
        for (int i = 0;i<(1<<num);i++) {
            boolean temp = true;
            for (int j = 0;j<num;j++) {
                if ((i&(1<<j))==0) continue;

                for (int k : graph.get(j)) {
                    if ((i&(1<<k))!=0){
                        temp = false; break;
                    }
                }
                if (!temp) break;
            }

            if (temp) indep.add(i);
        }

        //Use DP to count the number of DAGs in the given graph
        long[] dp = new long[1<<num]; //Number of DAGs in the subgraph on the set i of vertices
        dp[0] = 1;

        for (int i = 1;i<(1<<num);i++) {
            for (int j : indep) {
                if ((i|j)!=i) continue; //Ensures j is a subset of i

                int prev = i-j;
                dp[i] = (dp[i]+(int) Math.pow(-1,Integer.bitCount(j)+1)*dp[prev])%mod;
                dp[i] = (dp[i]+mod)%mod;
            }
        }

        long ans = (dp[(1<<num)-1]*m)%mod;
        ans = (ans%2==0) ? ans/2 : (ans+mod)/2;
        System.out.println(ans);
    }
}

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