No.1167 Graduation Trip
Problem Statement
Mitsubachi is planning a graduation trip lasting $N$ days in total.
Before day $1$ begins, Mitsubachi is at point $0$.
During this trip, Mitsubachi has decided to move according to an integer sequence $A_1, A_2 ,\ ...\ , A_N$ of length $N$.
On day $i$, he decides whether or not to use the integer $A_i$. If he uses it, letting point $j$ be his current position, he moves to point $j\ {\rm XOR}\ A_i$; if he does not use it, he stays where he is.
Note that even if his location does not change as a result of the move, it is treated as having moved.
You are given $Q$ queries; answer them. The $i$-th query is as follows.
長さ $M_i$ の整数列 $B_{i1}, B_{i2} ,\ ...\ , B_{iM_i}$ が与えられる。
$B_{i1}, B_{i2} ,\ ...\ , B_{iM_i}$ 日目と $N$ 日目を終えた時、それぞれすべてで地点 $0$ にいるような $N$ 日間の行動の仕方は何通りか。For each query, answer with the remainder when divided by $10^9+7$.
In this problem, ${\rm XOR}$ denotes the bitwise exclusive OR.
Input
$N\ \ Q$
$A_1\ \ A_2\ \cdots\ A_N$
$M_1$
$B_{11}\ \ B_{12}\ \cdots\ B_{1M_1}$
$M_2$
$B_{21}\ \ B_{22} \ \cdots\ B_{2M_2}$
$\ \vdots$
$M_Q$
$B_{Q1}\ \ B_{Q2} \ \cdots\ B_{QM_Q}$
All input values are integers.
$ 2 \leq N \leq 10^4$
$ 1 \leq Q \leq 10^4$
$ 0 \leq A_i < 2^{32}\ \ (1 \leq i \leq N)$
$ 1 \leq M_i \leq {\rm min}(N-1,\ 10)\ \ (1 \leq i \leq Q)$
$ 1 \leq B_{ij} \leq N-1\ \ (1\leq i \leq Q,\ 1\leq j \leq M_i)$
$ B_{ij} < B_{ij+1}\ \ (1\leq i \leq Q,\ 1\leq j < M_i)$
Output
Print the answers to the queries, $1$ per line, for a total of $Q$ lines. Print a newline at the end.
Sample
Sample 1
Input
3 1
1 1 2
1
2
Output
2
If he moves on day $1$ and day $2$ and does not move on day $3$, then since $0\ {\rm XOR}\ 1 = 1,\ 1\ {\rm XOR}\ 1 = 0$, he finally arrives at point $0$.
Another course of action satisfying the conditions is not moving on any day, so there are $2$ ways in total.
Sample 2
Input
6 3
0 0 0 0 0 0
1
2
3
2 3 4
2
3 4
Output
64
64
64
No matter how he acts, he remains at point $0$.
Sample 3
Input
50 3
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5 1
3
3 19 20
9
2 3 5 7 9 11 13 17 19
4
2 7 18 28
Output
877905026
134217728
294967268
Print the remainder when divided by $10^9+7$.
Source
Nada School 75th Class Junior High School Graduation Commemorative Contest: Graduation Trip
writer: Mitarushi
tester: Sashiming,karudano
Ported in accordance with HackerRank's terms. Some parts have been modified.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
蜜蜂