HackerEarth Ma5termind and XOR Minimization problem solution

In this HackerEarth Ma5termind and XOR Minimization problem solution Mastermind is a bright student of his class. To judge his intelligence and speed his teacher has given him a question and he needs your help for solving it. The question is :

Given a sequence of N elements, find all subsequences of this sequence, then compute the sum of all these subsequences individually, finally, find the number of subsequences that give minimum XOR with a given value A. He can solve this question very quickly but now he needs your help as the number of such questions is very large.

HackerEarth Ma5termind and XOR Minimization problem solution.

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<climits>
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long
#define VI vector<int>
#define PII pair<int,int>
#define VII vector<PII >
#define ft first
#define sd second
#define rz(v,n) v.resize(n)
#define VL vector<ll>
#define VLL vector<pair<ll,ll> >
#define PLL pair< ll,ll >
#define all(v) v.begin(),v.end()
#define IT iterator
// Input/Output
#define print(v) printf("%d\n",v)
#define printll(v) printf("%lld\n",v)
#define scan(v) scanf("%d",&v)
#define scanll scanf("%lld",&v)
// loops
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define RFOR(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,n) for(int i=0;i<n;i++)
//extra
#define ms(v,val) memset(v,val,sizeof(v))
#define fill(v,val) fill(all(v),val)
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define PIE 3.14159265358979323846264338327950
#define MOD 1000000007
#define ull unsigned long long
#ifdef ONLINE_JUDGE
 inline void inp( int &n )
 {
    n=0;
    int ch=getchar_unlocked();int sign=1;
    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}

    while(  ch >= '0' && ch <= '9' )
            n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
    n=n*sign;
  }
#else
inline void inp(int &n){
 cin>>n;
}
#endif

#define MAX 100001
#define TRIESIZE 2100001
ll DP[MAX];
bool S[MAX];
bool trie[TRIESIZE];
int P[21];
void process(){
  int i;
  P[0]=1;
  FOR(i,1,21)
      P[i]=P[i-1]*2;
}

void update(int x){
  int i;
  int idx=0;
  int p=1;
  RFOR(i,19,0){
    if(x&P[i]){
      trie[2*idx+2]=1;
      idx=2*idx+2;
    }else{
      trie[2*idx+1]=1;
      idx=2*idx+1;
    }
  }
}

int query(int x){
  int i;
  int sum=0;
  int idx=0;
  RFOR(i,19,0){
    if(x&P[i]){
      if(trie[2*idx+2])
        sum+=P[i],idx=idx*2+2;
      else
        idx=2*idx+1;
    }else{
      if(!trie[2*idx+1])
          sum+=P[i],idx=idx*2+2;
      else
        idx=idx*2+1;

    }
  }
  return sum;
}
int main(){

  #ifndef ONLINE_JUDGE
    f_in("in10.txt");
    f_out("out10.txt");
  #endif
  int t;
  t=1;
  while(t--){
   int n;
   inp(n);
   VI A(n);
   int i,j;
   S[0]=1;
   DP[0]=1;
   FOR(i,0,n) inp(A[i]);
   int maxx=1;
   FOR(i,0,n){
     for(j=maxx;j>=0;j--){
       if(S[j])
       {
         maxx=max(maxx,j+A[i]);
         S[j+A[i]]=true;
         DP[j+A[i]]+=DP[j];
         DP[j+A[i]]%=MOD;
       }
     }
   }
   process();
   int Q,x;
   inp(Q);
   FOR(i,1,MAX) if(S[i]) update(i);
   while(Q--){
     inp(x);
     int ans=query(x);
     printf("%d %lld\n",ans,DP[ans]);
   }
  }
  return 0;
}

Second solution

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 1000000007
#define NIL 0
#define MAXN 220001
#define EPS 1e-5
#define INF (1<<28)
typedef unsigned long long int uint64;
typedef long long int int64;
int sum[100005];
int a[105];
struct node{
    struct node *lchild,*rchild;
    node(){
        lchild=NULL;
        rchild=NULL;
    }
};
void ins(struct node *root,int val){
    for(int j=30;j>=0;j--){
        int x=val&(1<<j);
        if(x){
            if(root->rchild==NULL)
            root->rchild=new node();
            root=root->rchild;
        }
        else{
            if(root->lchild==NULL)
            root->lchild=new node();
            root=root->lchild;
        }
    }
}
int quey(struct node *root,int val){
    int ans=0;
    for(int j=30;j>=0;j--){
        int x=val&(1<<j);
        if(x==0){
            if(root->lchild){
                root=root->lchild;
            }
            else{
                ans|=(1<<j);
                root=root->rchild;
            }
        }
        else{
            if(root->rchild){
            ans|=(1<<j);
            root=root->rchild;}
            else
            root=root->lchild;
        }
    }
    return ans;
}
int main(){
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    sum[0]=1;
    for(i=0;i<n;i++){
        for(j=100000;j>=a[i];j--){
            if(sum[j-a[i]]){
            sum[j]+=sum[j-a[i]];
            if(sum[j]>=MOD){
                sum[j]%=MOD;
            }}}}    
    node *root=new node();
    for(i=1;i<=100000;i++){
        if(sum[i])
        ins(root,i);
    }
    int q,u,fin;
    scanf("%d",&q);
    while(q--){
        scanf("%d",&u);
        int ans=quey(root,u);
        printf("%d %d\n",ans,sum[ans]);
    }
    return 0;
}