시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 34 | 21 | 20 | 64.516% |
Suppose you are given two integers, m and n. You are also given a list of n distinct integers x1, x2, . . . , xn, with 0 ≤ xi ≤ 2m−1. For each number y from 0 to 2m−1, you’ve found the number py such that xpy has a maximum bitwise-XOR with y. That is, y ⊕ xpy >y ⊕ xi for all i=1..n, i ≠ py (⊕ means bitwise-XOR).
Now, consider the reverse problem. Given m, n, and the sequence p0, p1, . . . , p2m−1, count the number of sequences of distinct integers x1, x2, . . . , xn that could have generated that p sequence from the above algorithm. Two x sequences are different if there is some i such that xi in one sequence is different from xi in the other sequence. Output this count modulo 109+7.
Each test case will begin with a line with two space-separated integers m (0 ≤ m ≤ 16) and n (1 ≤ n ≤ 2m), where 2m is the length of the p sequence, and n is the length of the x sequences. Each of the next 2m lines will contain a single integer p (1 ≤ p ≤ n). These are the values of the sequence p0, p1, . . . , p2m−1, in order. Every value from 1 to n inclusive will appear at least once.
Output a single integer, which is the number of sequences x1, x2, . . . , xn which could have generated the sequence p0, p1, . . . , p2m−1 from the above algorithm, modulo 109+7.
3 6 1 1 2 2 3 4 5 6
4
2 3 1 2 1 3
0
3 8 1 2 3 4 5 6 7 8
1