No.462 The "Doesn't Know Day 6" Computer
タグ : / 解いたユーザー数 143
作問者 :
tatuyan_edson
/ テスター :
はむこ
Problem Statement
It is said that when counting off days on one's fingers, day 1, day 2, and so on, a miser cannot bear to open a clenched hand and therefore cannot count the 6th day. From this, a story has been handed down to the present day, in rakugo and elsewhere, that misers were colloquially called "those who don't know day 6".
A newly built computer represents non-negative integers in binary using \(N\) bits.
For example, when \(N=5\), \(14\) is \(01110\) and \(22\) is \(10110\).
This computer is a "doesn't know day 6" computer: when representing numbers in order, it does so by setting one bit at a time, and it hates returning a bit that has once been set to 1 back to \(0\). Therefore, what this computer can represent is a sequence of \(N+1\) non-negative integers that starts at \(0\) and ends at \(2^N-1\). For example, when \(N=4\), the sequence \(0,2,3,11,15\) is one example of a sequence that can be represented. On the other hand, even with the same \(N=4\), the sequence \(0,1,3,12,15\) cannot be represented.
Now, suppose you want to use this "doesn't know day 6" computer to represent \(k\) non-negative integers \(a_1,a_2,\cdots,a_k\). Write a program that finds how many sequences of \(N+1\) non-negative integers contain all of \(a_1\) through \(a_k\) and can be represented by the "doesn't know day 6" computer. However, when \(k=0\), all sequences satisfy the condition. Since the answer can be very large, output the remainder when divided by \(10^9+7\). If they cannot be represented, the count is \(0\).
Input
\(N\) \(k\) \(a_1\) \(a_2\) ... \(a_k\)
The first line contains the integers \(N\) and \(k\), separated by a single-byte space. \(1 \le N \le 60 \), \( 0 \le k \le N+1 \)
The second line contains \(k\) non-negative integers separated by single-byte spaces, which represent \(a_1,a_2,\cdots,a_k\) in order. Each of these values is at least 0 and at most \(2^N-1\), and no value appears more than once.
Note that when \(k=0\), the second line of input does not exist.
Output
Output only 1 line: the number of sequences of \(N+1\) non-negative integers that can be represented by the "doesn't know day 6" computer, as an integer, modulo \(10^9+7\).
Sample
Sample 1
Input
4 2 2 11
Output
2
There are 2 possible sequences: \(0,2,3,11,15\) and \(0,2,10,11,15\).
Sample 2
Input
10 3 5 1 3
Output
0
There is no sequence that contains all of \(5,1,3\) and can be represented by the "doesn't know day 6" computer.
Sample 3
Input
3 0
Output
6
Since \(k=0\), we consider all sequences that can be represented.
\(0,1,3,7\)
\(0,1,5,7\)
\(0,2,3,7\)
\(0,2,6,7\)
\(0,4,5,7\)
\(0,4,6,7\)
There are 6 sequences in total, as listed above.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。