Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). Denote the indices of bins having balls as $x_1, \cdots, x_{2k}$ in ascending order ($x_1 < x_2 < \cdots < x_{2k}$). We define the score of a configuration as $\oplus_{i=1}^{k}(x_{2i}-x_{2i-1}-1)$, where $\oplus$ is "bitwise exclusive or", or "xor". I'd like to count for each possible score, how many configurations are there?
Range: $n \leq 10^5, k \leq 50$. I've tried dynamic programming: let $f[i][j][s]$ be the number of configurations with $i$ bins, $2j$ balls, $s$ scores, but the time complexity is too high. I was wondering whether we may count the configuration more efficiently.
