Description：

给定 $N$ 和 $M$ ，问有多少个集合 $X,Y$ 满足：

$1$ 、 $\forall x_i\in X,x_i\in[1,N]$ ， $\forall y_i\in Y,y_i\in[1,M]$ 。

$2$ 、 $X\cap Y=\emptyset$

$3$ 、 $A=x_1\ xor\ x_2\ xor\dots xor\ x_n$ ， $B=y_1\ xor\ y_2\ xor\dots xor\ y_m$ ，有 $A<B$

$1\le N,M\le 2000$

Solution：

对于前两个条件，含义就是说每个数只能出现在一个集合里，问题在于第三个限制怎么做，发现 $A<B$ 等价于在 $A$ 和 $B$ 最高不相同的位 $A=0$ 而 $B=1$ ，但是问题在于如何确定这个最高不相同的位，可以枚举这一位，由于 $\text{xor}$ 操作的特殊性质，可以设状态为 $f[i][j][0/1]$ 表示做到了第 $i$ 个数，当前 $A\ \text{xor}\ B$ 是 $j$ ， $B$ 的第 $l$ 位为 $0/1$ 的方案数，转移时如果这个数给了 $A$ ，那么 $f[i][j\ \text{xor}\ i][0]+=f[i-1][j][0],f[i][j\ \text{xor}\ i][1]+=f[i-1][j][1]$ ，如果这个数给了 $B$ ，那么 $B$ 的第 $l$ 位可能改变，如果 $i$ 二进制下的第 $l$ 位是一，那么这个数给 $B$ 后 $B$ 的第 $l$ 位会发生变化，有转移： $f[i][j\ \text{xor}\ i][0]+=f[i-1][j][1],f[i][j\ \text{xor}\ i][1]+=f[i-1][j][0]$ ，否则 $B$ 不发生变化，有转移： $f[i][j\ \text{xor}\ i][0]+=f[i-1][j][0],f[i][j\ \text{xor}\ i][1]+=f[i-1][j][1]$ 。最后统计答案时，要求 $j$ 的最高位为 $l$ ，即 $j\in[2^l,2^{l+1})$ ， $ans$ 应加上 $f[max(N,M)][j][1]$ 。 $j$ 的范围要预处理 $2$ 的幂然后一步步增加。

另外不要先加再 $\%=$ ，直接加的时候模会快很多。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 2050

#define MOD 1000000007

int f[2][MAXN][2];

int bit[12];

int main()

{

	scanf("%d%d",&n,&m);

	register int ans = 0;

	bit[0] = 1;

	for(register int l = 1;l <= 11;++l)bit[l] = bit[l - 1] * 2;

	for(register int l = 0;l <= 10;++l)

	{

		memset(f,0,sizeof(f));

		register int cur = 0;

		f[cur][0][0] = 1;

		register int lim = 0;

		for(register int i = 1;i <= max(n,m);++i)

		{

			cur ^= 1;

			memset(f[cur],0,sizeof(f[cur]));

			while(i >= bit[lim])++lim;

			for(register int j = 0;j <= bit[lim];++j)

			{

				f[cur][j][0] = (f[cur][j][0] + f[cur ^ 1][j][0]) % MOD;

				f[cur][j][1] = (f[cur][j][1] + f[cur ^ 1][j][1]) % MOD;

				if(i <= n)

				{

					f[cur][j ^ i][0] = (f[cur][j ^ i][0] + f[cur ^ 1][j][0]) % MOD;

					f[cur][j ^ i][1] = (f[cur][j ^ i][1] + f[cur ^ 1][j][1]) % MOD;

				}

				if(i <= m)

				{

					if(i & (1 << l))

					{

						f[cur][j ^ i][0] = (f[cur][j ^ i][0] + f[cur ^ 1][j][1]) % MOD;

						f[cur][j ^ i][1] = (f[cur][j ^ i][1] + f[cur ^ 1][j][0]) % MOD;

					}

					else

					{

						f[cur][j ^ i][0] = (f[cur][j ^ i][0] + f[cur ^ 1][j][0]) % MOD;

						f[cur][j ^ i][1] = (f[cur][j ^ i][1] + f[cur ^ 1][j][1]) % MOD;

					}

				}

			}

		}

		for(register int j = (1 << l);j < (1 << (l + 1));++j)

		{

			ans = (ans + f[cur][j][1]) % MOD;

		}

	}

	printf("%d\n",ans);

	return 0;

}