preface
网上的题解看不懂，看代码看懂了 ：）
solution
考虑 \(\mathrm{x_i}\) 的倒数第 \(\mathrm{low_i - 1}\) 位到倒数第 \(\mathrm{1}\) 位可以乱选（选 \(\mathrm{0/1}\) 都满足 \(\mathrm{x_i \leq m_i}\)），那么就需要 \(\mathrm{x_i}\) 和 \(\mathrm{m_i}\) 的第 \(\mathrm{1}\) 位到倒数第 \(\mathrm{low_i + 1}\) 位都一样，然后 \(\mathrm{m_i}\) 倒数第 \(\mathrm{low_i}\) 位为 \(\mathrm{1}\)， \(\mathrm{x_i}\) 倒数第 \(\mathrm{low_i}\) 位为 \(\mathrm{0}\)。
令 \(\mathrm{k}\) 一共有 \(\mathrm{cnt}\) 位。
\(\mathrm{dp[i][j][k]}\) 表示考虑前 \(\mathrm{i}\) 个 \(\mathrm{x}\) 的取值，\(\mathrm{low_l}\) 的最大值为 \(\mathrm{j}\) （即前 \(\mathrm{j - 1}\) 位目前是确定的，因为\(\mathrm{x_{d} (1 \leq d \leq i)}\) 的前 \(j - 1\) 位都顶到上届，第 \(j\) 位为 \(0\) （\(\mathrm{low_d = j}\)） 或者 \(1\) （\(\mathrm{low_d < j}\)）），第 \(j\) 位的异或值为 \(k\)。
转移就是考虑 \(\mathrm{x_i}\) 前 \(\mathrm{d}\) 位都顶着上届，然后值得注意为了最后能等于 \(k\)，倒数 \(\mathrm{j}\) 位都必须留下一位来调整使这一位等于 \(k\) 的这一位，所以最终答案要除以 \(\mathrm{2^{j}}\)，当然也可以在过程中计算。
还有一种情况是选择 \(m_i\)，要特殊考虑，我调了好久 ：（。
//我看着，天真的我自己
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define MP(x,y) make_pair (x, y)
#define PII pair <int, int>
#define db double
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for (int i = (j); i <= (k); i++)
#define per(i,j,k) for (int i = (j); i >= (k); i--)
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
template <typename T>
void read (T &x) {
x = 0; bool fl_for_x = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {
if (ch == '-') fl_for_x = 0;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar ();
}
if (!fl_for_x) x = -x;
}
template <typename T, typename... Args>
void read (T &x, Args&... args) {
read (x), read (args...);
}
const int Maxn_For_Print = 30;
int Tp_For_Print, St_For_Print[Maxn_For_Print + 5];
template <typename T>
void write (T x) {
if (x == 0) {
putchar ('0');
return;
}
if (x < 0) {
x = -x;
putchar ('-');
}
while (x) {
St_For_Print[++Tp_For_Print] = x % 10;
x /= 10;
}
while (Tp_For_Print) {
putchar (St_For_Print[Tp_For_Print--] + '0');
}
}
template <typename T>
void print (T x, char ch) {
write (x), putchar (ch);
}
const int Maxn = 50;
const int Maxk = 31;
const LL Mod = 1e9 + 3;
int n, k;
int a[Maxn + 5];
LL f[Maxn + 5][Maxk + 5][2];
bool vis[Maxn + 5][Maxk + 5][2];
LL dfs (int step, int low, int val) {
//step 表示考虑 x[step] 的取值，low表示第一位到倒数第low位需要有数去修正，val表示需要修正的值（即之前的异或和）
val = val & (~((1 << low) - 1));
if (step == n + 1) return !val;
if (vis[step][low][val >> low & 1]) return f[step][low][val >> low & 1];
LL res = 0, tmp = 0;
per (i, Maxk, 0) {
//前 i 位顶着上届
if (a[step] >> i & 1) {
//第 i 位为 0，后面的乱选
//如果 i > low，那么 [low, i] 这几位就无法自己决定为 0 / 1，就是 solution 里为了最终异或值为 k 最后用来调整的那几位不能自由选，所以要比 Min (low, i)。
res = (res + dfs (step + 1, Max (low, i), val ^ tmp) * ((1ll << Min (low, i)) % Mod) % Mod) % Mod;
tmp |= (1 << i);
}
}
//都顶着上届，就是选择 m[i]
res = (res + dfs (step + 1, low, val ^ tmp)) % Mod;
f[step][low][val >> low & 1] = res, vis[step][low][val >> low & 1] = 1;
return res;
}
signed main () {
freopen ("C:\\Users\\Administrator\\Desktop\\lihan\\1.in", "r", stdin);
freopen ("C:\\Users\\Administrator\\Desktop\\lihan\\1.out", "w", stdout);
// freopen ("transport.in", "r", stdin);
// freopen ("transport.out", "w", stdout);
while (1) {
memset (f, 0, sizeof f);
memset (vis, 0, sizeof vis);
read (n, k);
if (!(n + k)) break;
rep (i, 1, n)
read (a[i]);
print (dfs (1, 0, k), '\n');
}
return 0;
}