2 3 1 2 3 4 1 2 3 3
1 4
题意：把这个数列取一些数分成两部分，要求x中所有数字都小于b中数字，求这些分配方案中，x里面的数全部“异或”起来的值等于y里面的数全部“与”起来的值相同的方案数，x和y中不能为空
做法，DP，用分割线的方法把数列分成两段，然后用x[i][j]来代表从开头知道第i个数字这些数字能组成的集合的总方案数，y[i][j]和x[i][j]差不多，但是有一点不同，就是当下标大于j的时候，x[j]中所有的方案x[i]中都存在，而在y[i]中，只记录和第i和数字进行了“与”运算的方案数，这样就不会重复了，因为我在y[i][j]的时候是和x[i-1][j]匹配，x[i-1][j]然后分割线左移的任何的x[i1][j1]的方案在x[i][j]中都有，所以我只在这个时候匹配一次
例如:
4
1 2 3 3
x[1]={1}
x[2]={1,2,1^2}
x[3]={1,2,3,1^2,1^3,2^3,1^2^3}
x[4]就不用计算了，因为去了第四个数字那么y里面就为空，违反条件了
y[4]={3}
y[3]={3,3&3} //这里的3是第三个数字的3，第四个数字的三在y[4]中出现并且已经与x[3]匹配过了，y[3]里面是从最后一个数字到第三个数字中和第三个数字3与运算得到的方案
y[2]={2,2&3,2&3&3}
在y[4]和x[3]匹配的时候就等于把y[4]与x[2]、y[4]与x[1]都匹配完了，毕竟x[3]包含了x[2],x[1]中所有的方案嘛
然后这个y[4]的方案就不用传递给y[3]了，不然又要与x[2],x[1]去匹配，这样就重复了，但是还是要保存式记录下来，因为前面随便一个数字都可以和它形成一个新的集合
这个题谁会相信我做了一天？当初要了解题意的时候找博客，结果只有三条，现在一下子就成几页了，而且我一直WA在一个代码，却在博客看到了一个和自己一模一样的代码，你应该要知道这种情况下我会怀疑他的也是WA，结果他的AC，我看了2小时都没看出所以然，结果让别人一看。。。我滴天那，1024我写成了1014，我擦你妹妹蛋蛋的，天坑
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL __int64
#define mod 1000000007
using namespace std;
LL x[1111][2222],y[1111][2222]; //x：分割线左边，y：分割线右边，如x[i][j]代表分割线在第i个数字和i+1个数字中间时候的异或结果是j的方案数
int main (void)
{
int t,n,i,j,k,l;
int s[1010];
scanf("%d",&t);
while(t--&&scanf("%d",&n))
{
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
for(i=1;i<=n;i++)
{
scanf("%d",&s[i]);
x[i][s[i]]=1; //单个元素也算一个方案
for(j=0;j<1024;j++) //遍历所有值，把前一条分割线的方案全部异或到当前分割线的方案中来
{
x[i][j]=(x[i][j]+x[i-1][j])%mod; //传递方案数，这就是x[i]包含了所有x[i-j](j>0)中方案数的原因
x[i][j^s[i]]=(x[i][j^s[i]]+x[i-1][j])%mod; //把这些方案异或当前的这个值得到的新的方案存起来
}
}
LL sum=0;
for(i=n;i>1;i--)
{
y[i][s[i]]=1; //单个元素也算一个方案
for(j=0;j<1024;j++) //遍历所有值
if(y[i+1][j]) //如果这个值为j的方案数存在
y[i][j&s[i]]=(y[i][j&s[i]]+y[i+1][j])%mod; //那么把这个方案跟当前元素与运算之后得到新方案
for(j=0;j<1024;j++) //把得到的所有新方案加起来
sum=(sum+x[i-1][j]*y[i][j])%mod;
for(j=0;j<1024;j++) //把先前的旧方案传递过来
y[i][j]=(y[i][j]+y[i+1][j])%mod;
}
printf("%I64d\n",sum);
}
return 0;
}
HDU--4901--The Romantic Hero,布布扣,bubuko.com
原文：http://blog.csdn.net/jingdianitnan/article/details/38358735