Cf750f1 thinking DP

The main idea of the topic :

Give you a sequence , Output the set of XOR and sum of all increasing subsequences .

for example ：
4
4 2 2 4
Output :
4
0 2 4 6

Because there are increasing subsequences :
0
2
4
2 4
Their XOR and set is 0 2 4 6

$n\le 1e5,a_i\le 500$

Topic ideas :

Simple thinking :$dp(i,j)$ On behalf of $i$ Number , Whether there is an XOR sum of increasing subsequences j.

But we need it to increase , So greedy let $dp(i,j)$ For XOR and for $j$ The smallest possible of the increasing subsequence of End value .

Then you can move .

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[maxn];
int dp[513] , g[513];
int main()
{
    
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    memset(dp , 0x3f , sizeof dp);
    dp[0] = 0;
    for (int i = 1 ; i <= n ; i++){
    
        memcpy(g , dp , sizeof g);
        for (int j = 0 ; j < 512 ; j++){
    
            if (g[j] < a[i]){
    
                int k = j ^ a[i];
                dp[k] = min(g[k] , a[i]);
            }
        }
    }
    vector<int> ans;
    for (int i = 0 ; i < 512 ; i++) if (dp[i] != inf) ans.push_back(i);
    cout << ans.size() << endl;
    for (auto g : ans) cout << g << " ";
    cout << endl;
    return 0;
}