BITSET优化dp

BZOJ3687 https://vjudge.net/problem/HYSBZ-3687

注意是所有子集和的异或和。

INPUT 
3
1 2 3
OUPUT
(1^2^3^3^4^5^6)
//不是(1^2^3^4^5^6)

#include<bits/stdc++.h>
using namespace std;
int n;
bitset<2000007>a;
int main(){
    cin>>n;
    a[0]=1;
    int sum;
    for(int i=1;i<=n;i++){
    int b;cin>>b;
    a=a^(a<<b);
    sum=sum+b;
    }
    int ans=0;
    for(int i=ans+1;i<=sum;i++)if(a[i])ans=ans^i;
    cout<<ans;
    return 0;
}

View Code

LibreOJ β Round #2 T2https://loj.ac/contest/4/problem/2

转移f[i]=f[i-1]|(f[i-1]<<xi*xi)