题目描述
给定一个长度为 N 的非负整数序列 A1,A2,…,AN 和一个正整数 M。对所有 i,0≤Ai<2M。
求满足以下条件的长度为 N 的序列 B 的个数。
- 对所有 1≤i≤N,0≤Bi<2M。
- 对所有 1≤i<N,$(A_i\mathbin{\&} B_i)\le(A_{i+1}\mathbin{\&} B_{i+1})$。
- 对所有 1≤i<N,$(A_i\mathbin{\vert} B_i)\ge(A_{i+1}\mathbin{\vert} B_{i+1})$。
& 表示按位与,∣ 表示按位或。答案对 109+7 取模。
输入格式
第一行两个正整数 N,M。第二行 N 个整数 A1,…,AN。
输出格式
一行一个非负整数,表示答案对 109+7 取模后的结果。
数据范围
1≤M≤30,1≤N≤100,0≤Ai<2M。
原赛采用捆绑测试,子任务如下。
| 子任务 |
特殊限制 |
原赛分值 |
| 1 |
N≤2 |
7 |
| 2 |
N≤5 |
12 |
| 3 |
N≤10 |
17 |
| 4 |
M≤10 |
25 |
| 5 |
N≤30 |
19 |
| 6 |
无 |
20 |
原 PDF 题面