[Solution] October 18, 2017

· · 题解

截至目前题解区均采用生成函数方式解决该问题，此处提供官方题解的组合意义做法。

这个做法很难想到，且需灵活运用部分线性代数知识，鄙人对着官解看了两天才终于看懂。官解式子的上下标似乎有点细节问题。

\text{Task}

题目链接：October 18, 2017。

在线性空间 \mathbb{F}_2^k 选出 n 个向量组成的向量组 a，使其张成空间内不包含向量 x。

\text{Solution}

当 x=0 时，相当于在线性空间中选出 n 个向量构成的线性无关组，故而答案为 \prod_{i=0}^{n-1}(2^k-2^i)。

当 x\not= 0 时，容易发现 x 具体为什么值对答案不产生影响（可以结合推导过程理解）。

前置知识：正交补空间。

前置结论：

以上结论读者不难自证可以自行查询相关证明。（因为证明部分我没太看懂。）

假设向量 x 恰在 k-i 维度空间内被舍弃，因而会进行 i 次降维，在前 i-1 次降维中强制保留 x，则方案数量为 \prod_{j=1}^{i-1}(2^{k-j}-1)，在第 i 次降维中需舍弃 x，方案数量为 2^{k-i} 种，此时 a 中每一元素均可在这个 k-i 维子空间内任取，方案数量为 (2^{k-i})^n 种。

也就是说，统计形如 (S_0,S_1,\dots,S_{i-1},S_i,a) 的多元组数量，满足：

由于 a 任取时，a 的张成空间可能低于 k-i 维，因此会算重，需要通过容斥处理。

综上，答案式如下（累乘符号下标大于上标时值视为 1）：

ans=\sum_{i=1}^{k}(-1)^{i-1}\cdot(2^{k-i})^n\cdot(2^{k-i}\cdot\prod_{j=1}^{i-1}(2^{k-j}-1))

因为刨除向量 x 至少需要丢弃一个维度，因此求和下标从 1 开始。

容易感性理解到以上式子是正确的，但在后半部分依然附上证明。

考虑证明以上容斥恰好将每个向量组 a 计算到一次，也就是说，每个 a 在如上容斥式子中对应的系数恰好为 1。由于 a 在以上式子中哪些会被统计到与其张成空间有关，因而设 a 的张成空间为 T，其大小为 t，此时计算上述多元组 (S_0,S_1,\dots,S_{i-1},S_i,a) 数量乘容斥系数后的和。

经过尝试发现，直接通过 T 计算以上空间组依然是不便的，故而考虑转换为对正交补空间进行统计，可以发现，原多元组 (S_0,S_1,\dots,S_{i-1},S_i,a) 与满足如下条件的多元组 (S'_0,S'_1,\dots,S'_{i-1},S'_{i},T) 形成双射：

当正交补空间包含向量 x 时，原空间不包含 x，因此将正交补空间对应回原空间，这个序列相当于反向考虑升维过程，枚举在哪个维度向量 x 被加入线性空间。

此时多元组数量的统计与前文是相同的，乘上前文统计时的容斥系数，因此只需证明以下式子成立（累乘符号下标大于上标时值视为 1）：

\sum_{i=1}^{k-t}((-1)^{i-1}\cdot 2^{k-t-i}\cdot\prod_{j=1}^{i-1}(2^{k-t-j}-1))=1 $$ \sum_{i=2}^{k-t}((-1)^{i-1}\cdot 2^{k-t-i}\cdot\prod_{j=1}^{i-1}(2^{k-t-j}-1))=1-2^{k-t-1} $$ 左右两侧同时除以 $(1-2^{k-t-1})$ 得： $$ \sum_{i=2}^{k-t}((-1)^i\cdot2^{k-t-i}\cdot\prod_{j=2}^{i-1}(2^{k-t-j}-1))=1 $$ 下标化为 $1$ 得： $$ \sum_{i=1}^{k-t-1}((-1)^{i-1}\cdot 2^{k-t-1-i}\cdot\prod_{j=1}^{i-1}(2^{k-t-1-j}-1))=1 $$ 此时式子即为原式上界为 $k-t-1$ 时的形式，归纳得出结论成立。 ## $\text{Code} 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e7+5;
const int MOD = 998244353;

int T, n, k, x;
int pw[N], d[N], g[N];

int qmont(int x, int k) {
    int rst = 1;
    while (k) {
        if (k & 1) rst = (LL)rst*x%MOD;
        x = (LL)x*x%MOD;
        k >>= 1;
    }
    return rst;
}

int main() {
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = pw[i-1]*2%MOD;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &k, &x);
        if (!x) {
            if (!k || n > k) printf("%d\n", 0);
            else {
                int rst = 1;
                for (int i = 0; i < n; i++)
                    rst = (LL)rst*(pw[k]-pw[i]+MOD)%MOD;
                printf("%d\n", rst);
            }
        } else {
            if (!k) printf("%d\n", 1);
            else {
                d[k] = 1;
                for (int i = k-1; i >= 0; i--) {
                    g[i] = (LL)pw[i]*d[i+1]%MOD;
                    d[i] = (LL)(pw[i]-1+MOD)*d[i+1]%MOD;
                }
                int rst = 0, now = 1, p = qmont(2, n);
                for (int i = 0; i < k; i++) {
                    rst += (LL)((k-i-1)&1 ? MOD-1 : 1)*g[i]%MOD*now%MOD;
                    (rst >= MOD) && (rst -= MOD);
                    now = (LL)now*p%MOD;
                }
                printf("%d\n", rst);
            }
        }
    }
    return 0;
}