Subtask 1

Since ~N \le 9~, we can simply try every single path by doing depth first search, and check if the edge is blocked before proceeding.

Runtime complexity: ~\mathcal O(K 2^N N^2)~

Subtask 2

Since ~N \le 1000~, we can create a matrix representing links (or blocked links) between people. Note that the ways to get to person #N is the sum of ways to get to person #i ~(1 \le i \le N)~ where ~i \to N~ is not blocked. Therefore, we can use dynamic programming to memorize the solutions for people before.

Runtime complexity: ~\mathcal O(N^2+KN)~

Subtask 3

The big difference from the last subtask is that the number of ways to add has gotten much larger, but the number of blocked links has not increased much. We can take advantage of this by maintaining the sum of all previous elements, and subtracting the blocked links instead. To avoid duplicate deletions, we can use a set or similar data structure to maintain all the unique blocked links for each person.

Runtime complexity: ~\mathcal O(N \log N \sum X^2)~

Subtask 4

Let us mark each person with a bitset (binary number) from ~0~ to ~2^K-1~ to indicate the sets covering it. A bit will be on to indicate the person is in the group, and off otherwise. Two people are in the same group only if they overlap on at least 1 bit. In other words, ~A \mathbin{\&} B \neq 0~. After we solve a person, we can store their path count inside an array of size ~2^K~. When we try to solve for another person, we can loop through the array and subtract from the indices that share at least one bit with the binary number of that person.

Runtime complexity: ~\mathcal O(N 2^K)~

Subtask 5

The same idea is used as subtask 4, however, we can't pass using the same method as ~2^{14}=16\,384~, which is way too big to run within the time limit. To get around this, we need to create a data structure which can efficiently update and query the sums from indices that share at least one bit.

To solve queries, we first need to update. To do this, we can split the ~14~-bit binary number into ~2~ pieces of ~7~ bits each. Let us call those part ~A~ and part ~B~.

First, we create an array of ~2*2^7*2^7~. Let us call it ~ds[2][2^7][2^7]~.

To update, we go through each integer ~i~ from ~0~ to ~2^7-1~. If ~A \mathbin{\&} i = 0~, update ~ds[0][i][B]~, otherwise update ~ds[1][i][B]~.

This way, ~ds[0][A][B]~ contains the sum of all numbers in the form ~XB~ where ~X \mathbin{\&} A = 0~. Meanwhile, ~ds[1][A][B]~ contains the sum of all numbers in the form ~XB~ where ~X \mathbin{\&} A \neq 0~.

First, we add ~ds[1][A][0 \dots (2^K-1)]~ since that contains all numbers that share a bit in the first ~7~ bits. To account for the remaining numbers that do not share the first ~7~ bits, but share some of the last ~7~ bits, we go through ~ds[0][A][j]~ for all ~j~ where ~j \mathbin{\&} B \neq 0~.

Using this data structure, we can update and query in ~2^{K/2}=\sqrt{2^K}~ time.

This is sufficient to solve for the last subtask.

Runtime complexity: ~\mathcal O(N \sqrt{2^K})~