Title:【Math teacher's homework】#
Description##
题目大意：给你n个数m1,m2...mn，求满足X1 xor X2 xor ... xor Xn=k，0<=Xi<=mi （1<=i<=m）的方案数
Input Format##
多组数据（至多100组）每组数据第一行包括两个整数n,k，第二行包括n个整数m1,m2...mn（1<=n<=50，0<=k,mi<=(2^{31}-1)(1<=i<=n)）
输入以0 0结尾
Output Format##
对于每组数据输出一行表示题目中描述的方案数，方案数可能很大，你只需输出方案数mod 1000000003的结果
Sample Input##
11 2047
1024 512 256 128 64 32 16 8 4 2 1
10 2047
1024 512 256 128 64 32 16 8 4 2
0 0
Sample Output##
1
0
Solution##
还是太菜了，这道题看了很很很很很久
废话不说了
首先，我们把mi+1,那么我们Xi的限制条件自然改变了，变成了1<=Xi<mi（1<=i<=n）
然后我们来分析一下如何进行数位DP
对于Xi，从高位开始比较，必然有若干个高位与mi相等，我们把相等的这些位涂成深蓝色，第一个与mi不同的位涂成绿色（由于Xi一定小于mi，mi的该位必然为1，Xi的该位必然为0）
如果该题没有限制，那么每一位异或为1或0的方案数应该都为(2^{n-1})，因为只要n-1个数随便取，用最后一个数改变异或值即可
也就是说，如果Xi已经确定了一位涂上了绿色，那么我们后面的格子就和没有限制是一样的了，那么我们只要固定每列的一个格子，其他格子便可以随便取了
由此我们规定每列最早出现的格子涂成橙色，其余格子涂成浅蓝色，那么，每一列的方案数就是(2^{浅蓝色格子数-1})
有了这些基础我们就可以设计状态了，f[i][j][l]表示处理到第i个数最左边的绿色格子在第j位第j列的异或值为l的方案数
枚举对于f[i][j][0/1]我们枚举上一行的状态f[i-1][k][l]，由上一行的状态来推出该行状态
我们用num[i][j]来存储mi的第j位数字（二进制下），用col[i][j]来记录第j位的数值从第一个数异或到mi的异或值，用b[i]表示(2^i)的值
接下来，分类讨论~~~
（1）当j>k时 f[i][j][col[i-1][j]]+=f[i-1][k][l]*b[k-1]，由于第j格在该行为绿色格子，即其值为0，后面的蓝色格子可以任意取，因此该方程很容易理解
（2）当j=k时 f[i][j][l]+=f[i-1][k][l]*b[j-1]，由于第j格在该行为绿色格子，即其值为0，且j,k位于同一列，后面的蓝色格子可以任意取，因此该方程很容易理解
（3）当j<k时 f[i][k][l^num[i][k]]+=f[i-1][k][l]*b[j-1]，由于第j格在该行为绿色格子，即其值为0，后面的蓝色格子可以任意取，因此该方程很容易理解
但是由于绿色格子只存在于原数该位值为1的位上，所以方程符合题意当且仅当num[i][j]=1
还有一件事，就是如果最左边的绿色格子如果在第j位，则比j高位的col[n]k都必须与mi的第k位相等
emmmmm，讲到这里，只要记得mod 1000000003应该就没问题了吧（细节错了不要怪我瞎讲）
附代码咯
#include<cstdio>
#define mo 1000000003
#include<cstring>
#define me(a) memset(a,0,sizeof a)
int k,num[55][33],n,m,b[32],col[55][33],f[55][33][2],ans,md[33];
void in(int i){scanf("%d",&k);k++;int t=0;for(;k;)num[i][++t]=k&1,k>>=1;}
int main(){
b[0]=1;
for (int i=1;i<=31;i++) b[i]=b[i-1]*2;
while (~scanf("%d%d",&n,&m)){
if (!n&&!m) return 0;me(col),me(f),me(num),ans=0;f[0][1][0]=1;
for(int i=1;i<=n;i++)in(i);
for(int i=1;i<=n;i++)for(int j=1;j<=32;j++)col[i][j]=col[i-1][j]^num[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=32;j++)if(num[i][j])
for(int k=1;k<=32;k++)
for(int l=0;l<=1;l++)if(f[i-1][k][l]){
if(j>k)f[i][j][col[i-1][j]]=(f[i-1][k][l]*1ll*b[k-1]+f[i][j][col[i-1][j]])%mo;
else if(j==k) f[i][j][l]=(f[i-1][k][l]*1ll*b[k-1]+f[i][j][l])%mo;
else f[i][k][l^num[i][k]]=(f[i-1][k][l]*1ll*b[j-1]+f[i][k][l^num[i][k]])%mo;
}
for(int i=1;i<=32;i++)md[i]=m&1,m>>=1;
for(int i=32;md[i+1]==col[n][i+1]&&i;i--)ans=(1ll*ans+f[n][i][md[i]])%mo;
printf("%d
",ans);
}
}