E. Zero
矩阵快速幂优化 dp。
考虑第一个数任意选，有 \(2^m\) 种选择，那么第 \(2\sim n-1\) 就有 \(2^{m-1}\) 种选择，因为最后要和前面的异或结果为 \(0\) ，所以最后一位是固定的，但是此时最后一位可能和倒数第二位相等，所以 \(1\sim n-2\) 的异或结果就肯定为 \(0\)，设 \(f_i\) 表示序列长度为 \(i\) 时的答案，那么转移方程为：
\[f_n = 2^m\cdot (2^m - 1)^{n-2} - f_{n-2} \cdot (2^m - 1)
\]
注意到 \(n\) 最大为 \(1\times10^9\)，那么可以采取矩阵快速幂优化转移。
则有：
\[
\begin{bmatrix}
f_{n} \\
f_{n-1} \\
f_{n-2} \\
(2^m-1)^{n-1}
\end{bmatrix} =
\begin{bmatrix}
0 & -(2^m-1) & 0 & 2^m \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 2^m-1
\end{bmatrix}
\begin{bmatrix}
f_{n-1} \\
f_{n-2} \\
f_{n-3} \\
(2^m-1)^{n-2}
\end{bmatrix}
\]
代码中 Z 类型为自动取模类。
using Z = ModInt<MOD[0]>;template<class T>
struct Matrix {i64 N;vector<vector<T>> A;Matrix() : N(0) {}Matrix(int n) : N(n), A(n, vector<T>(n, 0)) {}Matrix(const vector<vector<T>>& mat) {assert(!mat.empty() && !mat[0].empty()); // 确保非空N = mat.size();A = mat;}const vector<T>& operator[](int i) const {return A[i];}Matrix operator*(const Matrix &b) const {assert(N == b.N);Matrix res(N);for (int i = 0; i < N; i++) {for (int k = 0; k < N; k++) {T tmp = A[i][k];if (tmp == 0) {continue;}for (int j = 0; j < N; j++) {res.A[i][j] += tmp * b.A[k][j];}}}return res;}//快速幂实现Matrix power(Matrix res, i64 k) const {Matrix base = *this;while (k) {if (k & 1) {res = res * base;}base = base * base;k >>= 1;}return res;}
};void solve() {int n, m;cin >> n >> m;vector<Z> f(4);Z m2 = power<Z>(2, m);f[1] = 1, f[2] = 0;f[3] = m2 * (m2 - 1) - (m2 - 1);if (n <= 3) {cout << f[n] << "\n";return;}vector a(4, vector<Z>(4));auto base = a;a[0][1] = 1 - m2, a[0][3] = m2;a[1][0] = 1;a[2][1] = 1;a[3][3] = m2 - 1;base[0][0] = f[3], base[1][0] = f[2];base[2][0] = f[1], base[3][0] = (m2 - 1) * (m2 - 1);Matrix<Z> A(a);A = A.power(A, n - 4);A = A * base;cout << A[0][0] << "\n";}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}
)
