给定三个正整数 \(n, k, x\)，求满足以下条件的序列 \(a_{1...n}\) 的个数：
- 对于每一个 \(1 \leqslant i \leqslant n\)，\(0 \leqslant a_i < 2^k\)。
- 序列 \(a\) 没有异或和为 \(x\) 的非空子序列。
答案对 \(998244353\) 取模。
\(1 \leqslant n \leqslant 10^9, k \leqslant 5 \times 10^7, 0 \leqslant x < 2^{\min(64, k)}\)。
数学题。
转化题意，序列的每个元素等价于 \(\mathbb F_2^k\) 内的一个向量。因此我们需要选出 \(\mathbb F_2^k\) 内的 \(n\) 个向量，满足他们构成的空间内不存在向量 \(x\)，求选择方案。分情况讨论：
\(x=0\)
问题转为选出 \(\mathbb F_2^k\) 内 \(n\) 个线性无关的向量。
这是个经典问题，又可以转化成选出一个满秩的 \(n\times k \ 01\) 矩阵的方案数。
答案即为
证明类似这个，这里从略。
可以 \(O(k)\) 地计算答案。
\(x > k\)
容易发现在 \(\mathbb F_2^k\) 内任意向量等价。因此任意 \(x > k\) 的答案相同。不妨令 \(x = 1\)。我们令选出的 \(n\) 个向量与 \(1\) 构成一个 \((n+1) \times k\) 矩阵。
先不考虑dp。直接按组合意义容斥可得答案。
我们考虑不包含 \(x\) 的维度为 \(d\) 的向量空间的基底数量，同上可以得到计算式
然后考虑剩下的 \(n-d\) 个向量，他们应当被基底表出。考虑第 \(i\) 个向量能表出的向量可以表为 \((1 + 2^i x + 2^{2i} x^2 + \cdots)\)，于是立得答案为
\[\left[x^{n-d\ }\right]\prod_{i=0}^d (1 + 2^i x + 2^{2i} x^2 + \cdots) = \left[x^{n-d\ }\right]\prod_{i=0}^d \frac{1}{1 - 2^ix} \]如果你熟悉 \(\text{q-binomial}\)，那这玩意就等于是 \(q=2\) 的情况，于是立得
\[\left[x^{n-d\ }\right]\prod_{i=0}^d \frac{1}{1 - 2^ix} = {n\brack{n-d}}_ 2 = \frac { [n]_ 2! } { [n-d]_ 2 ! [d]_ 2!} = \frac{ \prod_{i=1}^n (2^i-1) }{ \prod_{i=1}^d (2^i-1) \prod_{i=1}^{n-d} (2^i-1) } \]答案即为
\[\sum_{d=0}^n \prod_{i=1}^d(2^k-2^i) \times {n\brack{n-d}}_ 2 \]如果你不熟悉 \(\text{q-binomial}\)，那就去熟悉
我们考虑表出 \(F(x) = \left[x^{n-d\ }\right]\prod_{i=0}^n \frac{1}{1 - q^ix}\)。用两种方式消掉 \(i=0\) 的项得到
两边取 \([x^n]\)，经过简单移项可得递推关系式。
然后考虑dp，设 \(f_{i,r}\) 为选了 \(i\) 个向量，当前矩阵的秩为 \(r\) 的方案数。我们考虑新加入的向量是否能被先前除 1 外的向量表出，立即有方程
\[f_{i,r} = f_{i-1,r} \times 2^{r-1} + f_{i-1,r-1} \times (2^k - 2^{r-1}) \]得到了 \(O(nk)\) 的做法。
考虑按第一维求和得到 \(F_r\)：
\[F_r(x) = \sum_{i=0} f_{i,r}x^i \]带入 \(f_{i,r}\) 递推式立得 \(F_r\) 递推式：
\[F_r(x) = \frac{(2^k - 2^{r-1})x}{1 - 2^{r-1}x} F_{r-1}(x) = \prod_{i=1}^r \frac{(2^k - 2^{i-1})x}{1 - 2^{i-1}x} =\frac{1}{2^k-1} \prod_{i=1}^r(2^k - 2^{i-1})x^r \prod_{i=1}^r \frac{1}{1 - 2^{i-1}x} \]答案即为
\[\sum_{r=1}^k[x^{n+1}]F_{r}(x) \]考虑记
\[G_r(x) = \prod_{i=1}^r \frac{1}{1 - 2^{i-1}x} \]容易发现这是 q
我们承接上面消最低次项的思路得到 \((1-x)F(x) = (1-2^{n+1}x) F(2x)\)，于是提取系数得 \([x^n]F_r(x) = \prod_{i=1}^n\frac{2^{n-i+1} - 1}{2^i-1}\)
于是这玩意就是一个 \(\text{q-binomial}\)，总贡献得到
转化形式求和得到
\[\sum_{r=0}^n \prod_{i=1}^r(2^k-2^i) \times {n\brack{n-r}}_ 2 \]可以发现这两种方式得到的答案是相同的。
直接模拟计算即可。预处理后单次计算答案复杂度 \(O(k)\)。
code
#include <bits/stdc++.h>
#define rep(i,a,b) for (register int (i) = (a); (i) <= (b); ++(i))
#define pre(i,a,b) for (register int (i) = (a); (i) >= (b); --(i))
using namespace std;
const int N = 1e7 + 10, K = 1<<15, mod = 998244353, inv2 = 499122177;
int T, n, k, x, pw[N], upw[K + 10], fac[N], ifac[N];
typedef long long ll; typedef __int128 lll;
struct FastMod { int m; ll b; void init(int _m) { m = _m; b = ((lll)1<<64) / m; } int operator() (ll a) {ll q = ((lll)a * b) >> 64; a -= q * m; if (a >= m) a -= m; return a; } } Mod;
int add(int a, int b) { return (a += b) >= mod ? a - mod : a; } int mul(int a, int b) { return Mod(1ll * a * b); } template <typename ...Args> int mul(int a, Args ...b) { return mul(a, mul(b...)); }
int qp(int a, int b) {
int ret = 1;
while (b) {
if (b & 1) ret = mul(ret, a);
a = mul(a, a);
b >>= 1;
} return ret;
}
void init(int n = N - 10) {
Mod.init(mod);
pw[0] = upw[0] = fac[0] = ifac[0] = 1;
rep(i,1,n) pw[i] = add(pw[i-1], pw[i-1]);
upw[1] = pw[K];
rep(i,2,K) upw[i] = mul(upw[i-1], upw[1]);
rep(i,1,n) fac[i] = mul(fac[i-1], mod + 1 - pw[i]);
ifac[n] = qp(fac[n], mod - 2);
pre(i,n-1,1) ifac[i] = mul(ifac[i+1], mod + 1 - pw[i+1]);
}
int qw(int x) {return mul(upw[x >> 15], pw[x & 32767]);}
int C(int n, int m) {
if (m < 0 or n < m) return 0;
return mul(fac[n], ifac[m], ifac[n-m]);
}
int solve() {
if (x == 0) {
int ret = 1, tmp = min(n-1, k);
if (n > k) return 0;
rep(i,0,n-1) ret = mul(ret, add(pw[k], mod - pw[i]));
return ret;
} else {
int tmp = 1, ans = 0, c = qw(n);
rep(i,0,k-1) {
tmp = mul(tmp, add(c, mod - pw[i]));
ans = add(ans, mul(tmp, C(k-1, i)));
} ans = add(qw(1ll * n * k % (mod - 1)), mod - ans);
return ans;
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> T;
init();
while (T--) {
cin >> n >> k >> x;
cout << solve() << '\n';
}
}