Mathematical ideas
Linearity of expectation: for any coefficients $a$ and $b$, and any random variables $X$ and $Y$, we have $\mathbb{E}[aX+bY] = a\mathbb{E}[X] + b\mathbb{E}[Y]$. This allows us to look at each bit separately, rather than the numbers as a whole, which greatly reduces the complexity.
(?) Markov Chains: The Markov chains used in this problem are so simple that no formal knowledge about them is required (and I don't actually use Markov chains terminology in the explanation below, except in a side note). However, they are very useful in more complex similar problems. A Markov Chain is a collection of states together with probabilities to transition from one state to another.
Solution
You can start by considering only one bit, say bit $k$. Let $X_k$ be the $k^{\text{th}}$ bit of $x$. Let $Y$ be the output, and $Y_k$ is its $k^{\text{th}}$ bit. Define $K_k$ similarly. Here, I index the lowest bit ($0^{\text{th}}$ power of 2) by 0, and the highest by $l$. If $X$ and $K$ are not the same length, we can add 0s in front.
Let's compute $\mathbb{P}[Y_k=1]$ for each $k$. Note that this gives us the expected value for this bit:
$$\mathbb{E}[Y_k] = 1\mathbb{P}[Y_k=1] + 0\mathbb{P}[Y_k=0]$$
We'll need the probabilities of what we'll get out if either 1 or 0 is passed to the RGN in $k^{\text{th}}$ position. For this, we define a 2 by 2 matrix T:
Let $T_{i,j}$ be the probability that probability that, if we get input bit i in the $k^{\text{th}}$ position in our RNG, and $K_k=j$, we'll get 1 in the output.
This can be precomputed for all $i$, $j$. For example, $T_{0,1} = \frac{A + C}{100}$, as both XOR and OR with produce 1 given inputs 0 and 1.
Let $P_{k, n}$ be the probability that the $k^{\text{th}}$ bit is 1 after it's been passed through $n$ RNGs. Clearly, $P_{k, 0} = X_k$ (this is either 0 or 1, depending on our starting bit).
Each next RNG changes that probability as follows:
$$P_{k, d + 1} = P_{k, d}T_{1,K_k} + (1 - P_{k, d})T_{0, K_k}$$
($1 - P_{k, d}$ is the probability to have a $0$)
This can be computed using dynamic programming.
Note that the distribution of the output bit depends only on the input bit and the corresponding bit of $K$, so there are only four possibilities for it. That is, there's no need to repeat the whole computation for each bit, but we can do it once for each of the four possibilities.
Side note: This is where we have the Markov chains. We have two states, 0 and 1. We start on the state given by $X_k$. We have two possible transition matrices (they're not T, but can be computed from it), and which one we use depends on $K_k$. We're interested in the probability to be in state 1 after $N$ transitions.
Let's call the output Y. We know the probability that $Y_k=1$, namely $P_{k, n}$. The expectation of a binary variable is the probability to get 1, so $\mathbb{E}[Y_k] = P_{k,n}$.
Finally, we can use the linearity of expectation to compute the expectation of Y:
$$
\mathbb{E}[Y] = \mathbb{E}[Y_0 + 2Y_1 + 2^2Y_2 + \dots + 2^lY_l] = \\
= \mathbb{E}[Y_0] + 2\mathbb{E}[Y_1] + \dots + 2^l \mathbb{E}[Y_l] = \\
= P_{0,n} + 2P_{1,n} + 2^2P_{2,n} + \dots + 2^lP_{l,n}
$$
