Let us first understand the property of **XOR operation**, $x \oplus x = 0$ i.e. if we add even number of elements to any set, its XOR value will remain same

First we define a solution to a simpler problem, then we define it for our original problem

**Problem** : Given a set $A$ of $n$ elements and value $X$, how many subsets $S$ of $A$ will give $XOR(S) \oplus X = 0$, where $XOR(S)$ represents **XOR** of elements of subset $S$. It is considered that $A_i,X < 2^{10}$ and $1 \le n \le 1000$

**Solution** : We first give a $O(n*2^{10})$ solution. As all the numbers are atmost 10 bits long, there are only $2^{10}$ possible XOR values. So we have state of DP as $\text{(index, XOR value)}$. So for every index we have to store result for every possible XOR value which results in $O(n*2^{10})$ space complexity and for each state we $2$ possible choices of move, which makes time complexity $O(2*n*2^{10})$ Generally we omit this $2$ in multiplication

Now let us define the recurrence relation, $f(i,j)$ as count of subsets of $A[i..n-1]$ such that there XOR values is $j$

If our $i$ reaches $n$, then we have no more elements left for consideration, so if $j$ becomes $0$, we have selected a correct subset and we return $1$ otherwise we return $0$

Now for $i \lt n $, we have 2 choices, either to include $A_i$ or not to include it

Thus our recurrence relation will be like,

$f(i,j) = \begin{cases}
1 & \text{if $i = n$ and $j = 0$}\\\
0 & \text{if $i = n$ and $j \ne 0$}\\\
\left[f(i+1,j) + f(i+1,j\oplus A_i)\right] & \text{if $i \lt n$}
\end{cases}
$

Now lets move back to our original problem, the only change in problem is constraint on $n$. So the problem statement will be like

**Problem** : Given a set $A$ of $n$ elements and value $X$, how many subsets $S$ of $A$ will give $XOR(S) \oplus X = 0$, where $XOR(S)$ represents **XOR** of elements of subset $S$. It is considered that $A_i,X < 2^{10}$ and $1 \le n \le 10^5$

**Solution** : Now our old $O(n*2^{10})$ solution will give TLE, so how can be improve our previous solution to get it accepted

As $A_i \le 2^{10}$, considering all same values will give a better result. Now why this works ?

Assume that we have two values $P$ and $Q$, then $P \oplus Q \oplus Q = P$, which means that from value $P$, if we have infinite count of $Q$, only possible XOR values are $P$ and $P \oplus Q$

Thus if we add even number of value $Q$ to a set having current XOR value $P$, then resulting set will have XOR value $P$ but if we add odd number of value $Q$, then XOR value is $P\oplus Q$

If a set $S$ consists of $m$ elements, then it has $2^m$ subsets, in which there are $2^{m-1}$ subsets with odd number of elements and $2^{m-1}$ subsets with even number of elements

Now for our solution, consider $cnt[i]$ represent the count of value $i$

We define $f(i,j)$ as number of subsets considering values $[i..2^{10}-1]$ having XOR values $j$

In this if $i$ reaches $2^{10}$ then we have no more values to consider, we return $1$ if $j = 0$, $0$ otherwise

Now the interesting part comes, we have 2 cases :

(i) $cnt[i] = 0$ : In this we cannot add $i$ so we have only option to move forward without considering the $i$, which results in $f(i+1,j)$

(ii) $cnt[i] \gt 0$ : In this if we want to consider $i$ then we can add it odd number of times which results in $f(i+1,j\oplus i) * 2^{cnt[i]-1}$ ways, but if we don't want to consider $i$ then we can add it even number of times which results in $f(i+1,j) * 2^{cnt[i]-1}$ ways

Thus our recurrence relation will be
$f(i,j) = \begin{cases}
1 & \text{if $i = 2^{10}$ and $j = 0$}\\\
0 & \text{if $i = 2^{10}$ and $j \ne 0$}\\\
f(i+1,j) & \text{if $i \lt 2^{10}$ and $cnt[i] = 0$}\\\
\left[f(i+1,j) + f(i+1,j\oplus i)\right]*2^{cnt[i]-1} & \text{if $i \lt 2^{10}$ and $cnt[i] \gt 0$}
\end{cases}
$

The answer for problem can be get by calling $f(0,X)$

I hope you get the recurrence relation now. If you face any problem please ask

Happy Coding :)