CF446E

直接给转化后的题意 ：
长度为 $2^n$ 的序列 $B_i=\text{lowbit}(i)$ ，特别的，$B_0=1$ ，还有一个长度为 $2^n$ 的序列 $A$ 。
求 $A\times B^t$，其中卷积定义为异或卷积。
$n\le 25,t\le 10^{18}$ 。

给个不需要 FWT，不需要矩阵的简单做法。

先去考虑如何求出 $B^t$。
相当于选出一个序列 $\bigoplus_{i=1}^t a_i=m$，然后贡献是 $\prod B_{a_i}$。
由于 $B_i$ 只和 $i$ 的最低位有关，然后注意到如果确定了一个数的最低位是 $i$，那么这个数的高位可以随便填来使得异或和为 $m$。
因此直接枚举所有 $a_i$ 的最低位的最小值，然后其他数都变成可以乱填，只是要求这个最低位的出现次数的奇偶性要满足 $m$ 的这一位。

这可以直接单位根反演一下，比如要选奇数个，那么方案就是：

$$\frac{(A+B)^t-(A-B)^t}{2}$$

从中也可以看出，$B^t$ 中，$\text{lowbit}$ 相同的数 $B^t_i$ 相同，直接求出这 $O(n)$ 个不同的取值。

最后需要卷上 $A$，直接二进制位翻转然后扔线段树上考虑两个子树相互的贡献即可。

最后总复杂度 $O(2^n+n^2\log t)$，注意异或和为 $0$ 的特殊处理，以及模数不是质数，需要使用 $\text{exgcd}$ 求逆元。

#define mid ((l + r) / 2)
#define lid p << 1, l, mid
#define rid p << 1 | 1, mid + 1, r
#define seg int p, int l, int r

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ll T;
  int n, m;
  cin >> n >> T >> m;
  V<mint> a(1 << (n + 1)), pw(n + 5, 1);
  For(i, 1, n) pw[i] = pw[i - 1] * 2;
  For(i, 0, m - 1) cin >> a[i];
  For(i, m, (1 << n) - 1) a[i] = a[i - m] * 101 + 10007;

  V<mint> f(n + 5);
  For(i, 0, n - 1) {
    For(j, 0, i) {
      mint A = pw[n - 1], B = pw[n - 1] * (n - 1 - j) + 1;
      mint s0 = (A + B).pow(T), s1 = (B - A).pow(T);
      if (j == i)
        f[i] += (s0 - s1) / pw[n - j];
      else
        f[i] += (s1 + s0 - 2 * B.pow(T)) / pw[n - j];
    }
  }

  mint F0 = (pw[n - 1] * n + 1).pow(T);
  For(i, 0, n - 1) F0 -= f[i] * pw[n - 1 - i];

  Vi cnt(1 << n);
  For(i, 0, (1 << n) - 1) {
    cnt[i] = (cnt[i >> 1] >> 1) | ((i & 1) << (n - 1));
    if (i > cnt[i]) swap(a[i], a[cnt[i]]);
  }
  For(i, 0, (1 << n) - 1) swap(a[i], a[i + (1 << n)]);

  auto dfs1 = [&](auto lf, seg, int D) -> mint {
    if (l == r) {
      mint res = a[p];
      a[p] *= F0;
      return res;
    }
    mint L = lf(lf, lid, D + 1), R = lf(lf, rid, D + 1);
    a[p << 1] += R * f[D], a[p << 1 | 1] += L * f[D];
    return L + R;
  };
  dfs1(dfs1, 1, 0, (1 << n) - 1, 0);

  int ans = 0;
  auto dfs = [&](auto lf, seg) -> void {
    if (l == r) {
      ans ^= a[p].d;
      return;
    }
    a[p << 1] += a[p], a[p << 1 | 1] += a[p];
    lf(lf, lid), lf(lf, rid);
  };
  dfs(dfs, 1, 0, (1 << n) - 1);

  cout << ans << '\n';
}