Hangdian multi School Game 1 question 3 backpack (XOR dp+bitset)

Problem description

Alice has a backpack m She now wants to fill it with something ！
Alice has n project , Each project has a volume v Me and value w I .
Can I go from n Select multiple items from the items , So that the backpack is completely filled （ That is, the total volume is equal to the backpack capacity ）？ If so , When the back package is full , What is the maximum XOR sum of the value of items in the backpack ？

Input

The first line contains integers T(T≤10)- The number of test cases .
The first line of each test case contains 2 It's an integer n,m（1≤n,m<2^10)— Quantity of articles , Backpack Capacity .
next n That's ok , Each row contains 2 It's an integer v I ,w I (1≤v I ,w I <2^10)— The number and value of the project . 

Output

For each test case , Output one line , If the backpack cannot be filled , Just output one line “-1”, Otherwise, the maximum output XOR The sum of the .

Sample input

1 5 4 2 4 1 6 2 2 2 12 1 14

Sample output

14

Ideas （ Copy the standard idea ） ： use bitset establish dp Array (f) In every one of them bitset Elements （f[j]) Store a 01 strand , Some one is 1 Indicates the capacity corresponding to this position m The XOR and of can be j, use g Array copy f, Then add one capacity at a time v Is equivalent to g Move left v（ Equivalent to volume increase v Time exclusive or and for j The situation of ） The state changes to f[j]|=g[j^m1]  （ Thank many schools for teaching me to be a man , Children never dare again ）

Code ：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
using namespace std;
const int N=1050;
int n,m;
bitset<N> f[N],g[N];

void init(){
		for(int i=0;i<=1024;i++){
			f[i].reset();
		}
		f[0][0]=1;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m;
		init();
		for(int i=0;i<n;i++){
			int v,m1;
			cin>>v>>m1;
			for(int j=0;j<1024;j++){
				g[j]=f[j]; 
				g[j]<<=v;// here g In initial state 
			}
			for(int j=0;j<1024;j++){
				f[j]|=g[j^m1];// here f For the last state, that is (j^m1)^m1==j  notes ：“（）” Inside is the initial state  
			}
		}
		int ans=-1;
		for(int i=0;i<1024;i++){
			if(f[i][m]) ans=i;
		}
		cout<<ans<<endl;
	}
	return 0;
}