状态转移并不是顺序执行的,是随机到某些位置,所以,需要保留上一个状态
题意是有一些支票,上面有不同的价格,两个人拿支票,要求每个人拿的支票的价值的异或值为相同,求两个人能拿支票的方法有多少种,每个人可以不拿支票
方法:
两个数相等,则两个数的异或值为0,所以只需要找一些数,是这些数的异或值为0即可。
所以对于每个物品来说有3种情况,两个人都不拿,A拿,B拿。
dp【2】【n】;2代表两种状态,由于状态转移的位置随机,所以要保留上一状态的值,n代表的是当前两个人所拿支票值的异或值结果。
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int N=16384; const int mod =1000000007; int dp[2][N]; int arr[10010]; int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) { scanf("%d",&arr[i]); } memset(dp,0,sizeof(dp)); dp[0][0]=1; int p=0; int q=1; for(int i=0;i<n;i++) { for(int j=0;j<N;j++) { dp[q][j]=dp[p][j]; } for(int j=0;j<N;j++) { dp[q][j^arr[i]]=((dp[p][j]*2%mod)+dp[q][j^arr[i]])%mod; } swap(p,q); } cout<<dp[p][0]<<endl; } return 0; }