21351번 - Mafia 다국어언어 제한함수 구현

문제

A mafia has infiltrated the city <insert name here>. This has made the police force of <insert name here> very confused, with accusations of corruption being made in every direction. The city's $N$ cops (which are numbered between 0ドル$ and $N - 1$) has made a number of accusations about other policemen. Each accusation is either:

1. Police number $i$ is an honest cop.
2. Police number $i$ is a corrupt cop.

An honest cop always tells the truth, while a corrupt cop always lies. In total, there has been $M$ accusations.

The chief of police is now trying to fix the situation, starting with determining how many of her police men are corrupt. She has $G$ different guesses about the number of corrupt cops, and for each such number $C,ドル she wants to know how many different sets of size $C$ can be corrupt (where all the remaining cops are honest), given that all accusations are consistent.

예제

Let there be $N = 3$ cops, and two accusations. The first cop accused the second cop of being corrupt, and the second cop accused the third cop of being corrupt. There are two cases: either the second cop is corrupt or not.

If the second cop is corrupt, then he lies (so the third cop is honest), and the first cop did not lie (meaning he too is honest).

If the second cop is honest, then the third cop must certainly be corrupt (since the second cop's accusation is now true), and the first cop must be corrupt (since his accusation was a lie).

There are thus two possible subsets of corrupt cops: $\{1, 3\}$ and $\{2\},ドル meaning there is one subset of size 1 and one of size 2.

문제

Your task is to compute, for each of the police chief's guesses $C,ドル in how many ways there can be exactly $C$ corrupt cops. You should implement the functions cops(N, M, A, B, T) and guess(C).

• cops(N, M, A, B, T) - this function will be called exactly once by the judge at the start of the execution.
  • N: the number of cops.
  • M: the number of accusations.
  • A: an array with $M$ elements. A[i] (0ドル \le i < N$) contains the number of the cop who made the $i$:th accusation.
  • B: an array with $M$ elements. B[i] (0ドル \le i < N$) contains the number of the cop who is the target of the $i$:th accusation.
  • T: an array with $M$ elements. T[i] (0ドル \le i < N$) contains 1 or 2 if the $i$:th accusation is of type 1 or 2, respectively.
  • The function has no return value.
• guess(C) - this function will be called once for every guess.
  • C: a number between 0ドル$ and $N$; the guess of the police chief.
  • The return value of the function will never exceed 10ドル^{18}$.
  • The function should return the number of possible sets of corrupt cops of size $C,ドル where the remaining cops are honest.

A code skeleton containing the functions to be implemented, together with a sample grader, can be found at attachments.zip.

입력

The sample judge reads input in the following format:

• line 1ドル$: N M
• line 2ドル$: A[0] ... A[M - 1]
• line 3ドル$: B[0] ... B[M - 1]
• line 4ドル$: T[0] ... T[M - 1]
• line 5ドル$: G: the number of calls made to guess(C).
• line 6ドル$ C1 ... CG: the parameters of the $G$ calls to guess(C).

출력

The sample judge will write $G$ lines with the return values of guess(C).

제한

Let $G$ be the number of calls to guess(C).

• $N \le 2,000円$
• $M \le 70,000円$
• $G \le 2,000円$

힌트