Codeforces Round ＃750 (Div. 2) F.Korney Korneevich and XOR (easy＆＆hard version)(dp)

subject

The length is n Sequence , The first i The values are ai,

easy：n<=1e5,0<=ai<=500

hard：n<=1e6,0<=ai<=5000

For all strictly ascending subsequences in the sequence ,

The values of each sequence are XORed , Get a value v,

Output v The number of species , Output all in ascending order v The possibility of

Source of ideas

quality Code （hard）

Answer key

easy：

violence bitset Maintain reachable sets , Every violent XOR ,1e5*500*500/64

dp[i] Indicates that the current XOR is out i Sequence minimum of

hard：

dp[i][j] Indicates that the current sequence ends with i when , Subsequences can be XOR j when , End value of subsequence i The minimum position of

In actual implementation , Due to the need to transfer according to the prefix , The actual need does not exceed i

Experience

The feeling still uses the essence of strict ascending subsequence ,

Or the last value of the subsequence is as small as possible ,

Or when the same value is reached, the position should be as far forward as possible

Code 1（easy）

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> 
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int N=515,INF=0x3f3f3f3f;
int ans[N],c;
int n,now[N],v;
int main(){
    memset(now,INF,sizeof now);
    now[0]=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&v);
        for(int j=0;j<512;++j){
            if(now[j]<v){
                now[j^v]=min(now[j^v],v);
            }
        }
    }
    for(int j=0;j<512;++j){
        if(now[j]<INF){
            ans[++c]=j;
        }
    }
    printf("%d\n",c);
    for(int i=1;i<=c;++i){
        printf("%d%c",ans[i]," \n"[i==c]);
    }
    return 0;
}

Code 2（hard）

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> 
#include <cmath>
#include <vector>
#include <bitset>
using namespace std;
const int N=5e3+1,M=8192,INF=0x3f3f3f3f;
//dp[i][j]: Subsequence tail <=i when ,  Can be exclusive or out j The smallest sequence position of 
int n,v,dp[N][M],ans[M],c;
vector<int>pos[N];
int main(){
    memset(dp,INF,sizeof dp);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&v);
        pos[v].push_back(i);
    }
    dp[0][0]=0;
    for(int i=1;i<N;++i){
        for(int j=0;j<M;++j){
            dp[i][j]=dp[i-1][j];
            if(pos[i].empty())continue;
            if(i==j){
                dp[i][j]=min(dp[i][j],pos[i].front());
            }
            int id=upper_bound(pos[i].begin(),pos[i].end(),dp[i-1][j^i])-pos[i].begin();
            if(id!=pos[i].end()-pos[i].begin()){
                dp[i][j]=min(dp[i][j],pos[i][id]);
            }
        }
    }
    for(int j=0;j<M;++j){
        if(dp[N-1][j]!=INF){
            ans[++c]=j;
        }
    }
    printf("%d\n",c);
    for(int i=1;i<=c;++i){
        printf("%d%c",ans[i]," \n"[i==c]);
    }
	return 0;
}