问题分析

我们需要计算从 $[1, 2^m)$ 中选出 $n$ 个互不相同的正整数，使得它们的异或和为 $0$ 的方案数。这是一个经典的组合计数问题，涉及异或运算的线性代数性质。

算法思路

核心思想：组合计数 + 中国剩余定理

利用异或空间的线性代数性质，将问题转化为组合计数问题，并使用中国剩余定理处理模 $10^k$ 的运算。

关键数学公式

根据线性代数理论，在 $\mathbb{F}_2^m$ 中选取 $n$ 个不同向量且异或和为 $0$ 的方案数为：

$$\text{Answer} = \frac{1}{2^m} \left[ \binom{2^m-1}{n} + (-1)^{n+1} \binom{2^{m-1}-1}{\lfloor n/2 \rfloor} \right] $$

其中需要仔细处理整除性和模运算。

代码详解

1. 多项式与模运算基础

代码实现了完整的多项式运算和模运算系统：

struct poly {
    vector<int> v;
    // 多项式基本运算：加、减、乘、移位等
};

2. 扩展卢卡斯定理

由于 $n$ 很大且模数 $10^k$ 不是质数，需要使用扩展卢卡斯定理计算组合数：

inline int calc(int n, int p, int k) {
    if (!n) return 1;
    int ret = calc(n / p, p, k);
    ret = (ll)ret * quick_pow(query(mod - 1, p, k), n / mod) % mod;
    ret = (ll)ret * query(n % mod, p, k) % mod;
    return ret;
}

3. 主要计算函数

模 2 的计算

inline int calc2() {
    int mod1 = qpow(2, k + m), mod2 = qpow(2, k);
    int sgn = (((n + 1) >> 1) & 1) ? 1 : (mod1 - 1);
    
    // 计算分子部分
    int fz = (C(qpow(2, m) - 1, n, 2, k + m) + 
              (ll)sgn * C(qpow(2, m - 1) - 1, n >> 1, 2, k + m)) % mod1;
    fz >>= m;  // 除以 2^m
    
    // 最终结果
    int ret = (C(qpow(2, m) - 1, n, 2, k) - 
               (ll)(qpow(2, m) - 1) * fz) % mod2;
    return (ret + mod2) % mod2;
}

模 5 的计算

inline int calc5() {
    int mod1 = qpow(5, k);
    int sgn = (((n + 1) >> 1) & 1) ? 1 : (mod1 - 1);
    
    // 计算分子部分
    int fz = (C(qpow(2, m) - 1, n, 5, k) + 
              (ll)sgn * C(qpow(2, m - 1) - 1, n >> 1, 5, k)) % mod1;
    fz = (ll)fz * Inv(qpow(2, m), mod1) % mod1;  // 除以 2^m
    
    // 最终结果
    int ret = (C(qpow(2, m) - 1, n, 5, k) - 
               (ll)(qpow(2, m) - 1) * fz) % mod1;
    return (ret + mod1) % mod1;
}

4. 中国剩余定理合并

int main() {
    cin >> n >> m >> k;
    int mod1 = qpow(2, k), mod2 = qpow(5, k);
    printf("%lld\n", CRT((calc2() + mod1) % mod1, mod1, 
                        (calc5() + mod2) % mod2, mod2));
    return 0;
}

算法原理

组合计数推导

设 $V = \mathbb{F}_2^m$ 是 $m$ 维二元向量空间，大小为 $2^m$。我们需要计算大小为 $n$ 的子集 $S \subseteq V$ 满足 $\oplus_{v \in S} v = 0$ 的数量。

使用生成函数和容斥原理，可以得到闭式解。关键观察是：异或和为零的集合可以对应到某个线性子空间上的特定结构。

模运算处理

由于 $10^k = 2^k \times 5^k$，且 $2^k$ 和 $5^k$ 互质，可以使用中国剩余定理：

1. 分别计算答案模 $2^k$ 和模 $5^k$
2. 使用 CRT 合并结果

扩展卢卡斯定理

对于大组合数 $\binom{n}{m} \bmod p^k$，使用扩展卢卡斯定理：

$$\binom{n}{m} = \frac{n!}{m!(n-m)!} \times p^{\text{指数调整}} $$

其中阶乘计算使用递归分解。

复杂度分析

时间复杂度

• 组合数计算：$O(k \log n)$ 使用扩展卢卡斯定理
• 多项式运算：$O(k^2)$ 由于 $k \leq 18$
• 总复杂度：在数据范围内完全可行

空间复杂度

• $O(k^2)$：存储多项式系数
• $O(k)$：递归栈深度

关键优化

1. 多项式预计算

预计算阶乘多项式，加速组合数计算。

2. 位运算优化

利用 $2$ 的幂次性质，简化模 $2^k$ 的计算。

3. 递归分解

将大数计算分解为小数计算，避免直接处理大数。

正确性保证

数学严谨性

• 基于线性代数的严格推导
• 扩展卢卡斯定理的正确实现
• 中国剩余定理的准确应用

边界情况处理

• $n = 0$ 的特殊情况
• 模运算的符号处理
• 大数计算的溢出预防

总结

本题通过深入的组合数学分析和精巧的算法设计，解决了大规模异或和计数问题。算法的核心创新在于：

1. 理论突破：将异或和计数转化为组合数学问题
2. 工程实现：扩展卢卡斯定理的高效实现
3. 模运算技巧：中国剩余定理的灵活应用

该解法体现了数论、组合数学和算法设计的完美结合，是解决此类模运算组合计数问题的典范。