No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
タグ : / 解いたユーザー数 50
作問者 : 👑
Kazun
/ テスター :
👑 Note
The Time Limit for this problem is $1000$ ms.
Problem Statement
You are given $19$ integer sequences $A_1, \dots, A_{19}$. For $i=1,2, \dots, 19$, $A_i$ has length $L_i$ and $A_i=(A_{i,1}, \dots, A_{i,L_i})$.
A permutation $P=(P_1, \dots, P_{19})$ of $(1,2, \dots, 19)$ is called a wonderful permutation if it satisfies the following.
- For every integer $i$ between $1$ and $19$, inclusive, there exists an integer $j$ between $1$ and $L_i$, inclusive, such that $P_i=A_{i,j}$.
Also, for a permutation $P$ of $(1,2, \dots, 19)$, define $t(P)$ as follows.
Then, if $t(P)$ is even, $P$ is called a fair permutation, and if $t(P)$ is odd, $P$ is called a strange permutation.
Find the number $X_{{\rm even}}$ of fair wonderful permutations and the number $X_{{\rm odd}}$ of strange wonderful permutations.
Note that, in this problem statement, $(1,2, \dots, 19)$ means $(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19)$.
Constraints
- $0 \leq L_i \leq 19 \quad (1 \leq i \leq 19)$
- $1 \leq A_{i,1} \lt \dots \lt A_{i,L_i} \leq 19 \quad (1 \leq i \leq 19)$
- All input values are integers.
Input
$L_1$ $A_{1,1}$ $\cdots$ $A_{1,L_1}$
$\vdots$
$L_{19}$ $A_{19,1}$ $\cdots$ $A_{19,L_{19}}$
Output
Output $X_{{\rm even}}, X_{{\rm odd}}$ in this order, separated by a space. That is, output in the following format.
$X_{{\rm even}}$ $X_{{\rm odd}}$
Sample
Sample 1
Input
2 1 2 2 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19
Output
1 1
The wonderful permutations are $(1,2,3,4,5, \dots, 19), (2,1,3,4,5, \dots, 19)$, which makes $2$ in total. For each of them, we have the following.
- When $P=(1,2,3,4,5, \dots, 19)$, we have $t(P)=0$. Thus, $P$ is a fair wonderful permutation.
- When $P=(2,1,3,4,5, \dots, 19)$, we have $t(P)=1$. Thus, $P$ is a strange wonderful permutation.
Sample 2
Input
4 2 3 4 5 4 1 3 4 5 4 1 2 4 5 4 1 2 3 5 4 1 2 3 4 7 11 12 13 14 16 17 19 5 8 9 10 15 18 5 7 9 10 15 18 5 7 8 10 15 18 5 7 8 9 15 18 7 6 12 13 14 16 17 19 7 6 11 13 14 16 17 19 7 6 11 12 14 16 17 19 7 6 11 12 13 16 17 19 5 7 8 9 10 18 7 6 11 12 13 14 17 19 7 6 11 12 13 14 16 19 5 7 8 9 10 15 7 6 11 12 13 14 16 17
Output
86476460 86476320
Sample 3
Input
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
0 0
There may exist $i$ such that $L_i=0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。