#P6937. 序列

    ID: 6768 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-区间 DP数位 DP双射计数乘法原理一维前缀和滚动数组

序列

题目描述

给定一个长度为 NN 的非负整数序列 A1,A2,…,ANA_1,A_2,\ldots,A_N 和一个正整数 MM。对所有 ii,0≤Ai<2M0\le A_i<2^M。

求满足以下条件的长度为 NN 的序列 BB 的个数。

  1. 对所有 1≤i≤N1\le i\le N,0≤Bi<2M0\le B_i<2^M。
  2. 对所有 1≤i<N1\le i<N,$(A_i\mathbin{\&} B_i)\le(A_{i+1}\mathbin{\&} B_{i+1})$。
  3. 对所有 1≤i<N1\le i<N,$(A_i\mathbin{\vert} B_i)\ge(A_{i+1}\mathbin{\vert} B_{i+1})$。

&\& 表示按位与,∣\vert 表示按位或。答案对 109+710^9+7 取模。

输入格式

第一行两个正整数 N,MN,M。第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

输出格式

一行一个非负整数,表示答案对 109+710^9+7 取模后的结果。

数据范围

1≤M≤301\le M\le30,1≤N≤1001\le N\le100,0≤Ai<2M0\le A_i<2^M。

原赛采用捆绑测试,子任务如下。

子任务 特殊限制 原赛分值
1 N≤2N\le2 7
2 N≤5N\le5 12
3 N≤10N\le10 17
4 M≤10M\le10 25
5 N≤30N\le30 19
6 无 20

原 PDF 题面