Submission #1011146

#TimeUsernameProblemLanguageResultExecution timeMemory
1011146Oz121Amusement Park (CEOI19_amusementpark)Java
63 / 100
3017 ms29700 KiB
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 boolean[] indep = new boolean[1<<num]; Arrays.fill(indep, true); for (int i = 0;i<(1<<num);i++) { for (int j = 0;j<num;j++) { if ((i&(1<<j))==0) continue; for (int k : graph.get(j)) { if ((i&(1<<k))!=0) indep[i] = false; } } } //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 = 1;j<(1<<num);j++) { if ((i|j)!=i||!indep[j]) 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; } } //System.out.println(Arrays.toString(dp)); long ans = (dp[(1<<num)-1]*m)%mod; ans = (ans%2==0) ? ans/2 : (ans+mod)/2; System.out.println(ans); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...