In this answer, @animan123 explained that an inclusion-exclusion algorithm can be used to get a O(M*2^M) solution to SEAKAM. I also figured this out on my own during the contest, but I only got an AC on the second subtask, but on the rest, I got WA. Can someone explain why I got a WA on these subtasks? I have tried comparing subtasks between my solution and @animan123’s, but I can not find a subtask where we have different answers. I have tried testing solutions where the answer is 0, M is 0, and where there are cycles in the pairs (e.g.
1 2
,
2 3
, and
1 3
). I have tried N from 1<=N<=10 and N=100,000.
Since I got Subtask 1 wrong, there is definitely a subtask between 1<=N<=10 that I got wrong. If someone could help me find such a subtask, it would be very appreciated. Thank you!