简述题意：有一个长度为 \(n\le 10^5\) 的序列 \(a_i\) 以及一个整数 \(1\le m\le 50\)，满足 \(0\le a_i\le 2^m\)。给你一个整数 \(T\le 10^{16}\)，求出有多少个 \(1\le t\le T\)，使得 \(\bigg((a_1+t)\bmod 2^m\bigg)\oplus \bigg((a_2+t)\bmod 2^m\bigg)\oplus\dots\oplus\bigg((a_n+t)\bmod 2^m\bigg)=S\)，其中 \(S\) 是给定的一个值。
注意到 \(\bmod 2^m\) 等价于保留二进制的低 \(m\) 位，因此合法的 \(t\) 关于 \(2^m\) 会形成周期，因此我们只需要考虑 \(\min(2^m-1,T)\)，内的 \(t\)。令 \(dp(R)\) 代表限制 \(t\le R\) 的合法 \(t\) 个数，实际上答案就是 \(dp(2^m-1)\times \frac{T}{2^m}+dp(T\bmod 2^m)\)，当然注意如果 \(t=2^m\) 转一圈回到原来的位置仍合法的话，我们就多算了一位，因此要减去一。
考虑快速计算 \(dp(R)\)。我们发现某一位的 \(t\) 填 \(0/1\) 是否合法，其实只取决于这一位 \(1\) 的个数，但是上一位的 \(t\) 有可能会通过进位对这一位造成影响，因此我们需要记录某一个 \(a_i\) 是否进位。需要维护的信息过于复杂，考虑压缩状态，实际上我们发现加上同一个 \(t\) 之后，会造成进位的 \(a_i\) 一定是「按这一位后面的数排序之后的一段后缀」，即数大的才有可能进位。因此我们只关心上一位对这一位造成了 几个进位，就可以通过排序后的后缀得到哪些 \(a_i\) 有进位。
我们先将所有位后面的数排序。令 \(sa_{j,i}\) 代表，现在只考虑 \(a_i\) 的二进制后面 \(j\) 位，其它扔掉，然后按照大小排序的第 \(i\) 大的编号。这可以通过利用 \(sa_{j-1,i}\) 做一遍值域为 \(2\) 的基数排序得到。再令 \(cnt1_{j}\) 代表有多少个 \(a_i\) 第 \(j\) 位为 \(1\)。以上便是所有预处理，现在考虑设计数位 dp 状态。
令 \(dp_{l,x,0/1}\) 代表，考虑到了低 \(l\) 位，\([0,l-1]\) 位已符合要求，且第 \(l-1\) 位对第 \(l\) 位造成了 \(x\) 个进位，且当前的 \(t\) 是否已经超过了 \(R\) 的上界，\(t\) 的方案数。初值为 \(dp_{0,0,0}=1\)，答案就是考虑枚举第 \(m-1\) 位对第 \(m\) 位的进位数，当然不能超上界，即 \(\sum\limits_{i=0}^ndp_{m,i,0}\)。考虑刷表转移，即用 \(dp_{l,x,0/1}\) 去更新第 \(l+1\) 位的 \(dp\) 值。
再令 \(s\) 代表在进了 \(x\) 位之后，第 \(l\) 位 \(1\) 的个数；令 \(c\) 代表在进了 \(x\) 位之后，\(x\) 位产生的进位个数。 转移的时候，我们先枚举 \(l,0/1\)，再枚举 \(x\)，这是因为我们需要动态更新 \(s,c\)。考虑当前这位 \(t_l\) 填 \(0/1\) 能否产生贡献，先考虑 \(t_l=0\) 的情况，也就是说此时这一位的 \(1\) 个数没变，即 \(s\)。那么转移就是 \(dp_{l+1,c,type}\leftarrow dp_{l,x,0/1}\)，转移条件是 \(S_l\equiv (s\bmod 2)\)；再考虑 \(t_l=1\) 的情况，此时这一位 \(1\) 的个数发生了「取反」，即变成了 \(n-s\)，那么转移就是 \(dp_{l+1,s+c,type}\leftarrow dp_{l,x,0/1}\)，转移条件是 \(S_l\equiv ((n-s)\bmod 2)\)。
在转移结束后，我们要动态更新 \(s\) 和 \(c\)，具体来说考虑第 \(l-1\) 位向 \(l\) 多进了一位，那么我们就需要考虑 \(sa_{l-1,x+1}\)（上文提过，造成进位贡献的是按照后缀大小排序的）的这一位是否为 \(1\)，如果这一位为 \(1\)，那么进位之后第 \(l\) 位的 \(1\) 就没了，因此 \(s\) 减一，\(c\) 加一；否则 \(s\) 加一。
至此，我们在 \(O(nm)\) 的复杂度内解决了本问题。