题解：「ROI 2023 Day1 T4」Ультра mex

问题分析

本题要求统计满足以下条件的集合 ( A_0 ) 的个数：

• ( A_0 ) 包含 ( n ) 个不同元素（范围 ( 0 \sim 2^k-1 )），且必须包含 0；
• ( A_0 ) 是 mex-稳定的；
• ( A_0 ) 的 mex-极限等于 ( p )。

核心在于分析 mex-稳定 和 mex-极限 的性质，结合组合数学和数论变换（NTT）高效计算。

关键概念与性质

1. mex 函数：集合中未出现的最小非负整数，记为 ( \operatorname{mex}(A) )。
2. ultra 运算：若 ( m = \operatorname{mex}(A) )，则 ( \operatorname{ultra}(A) = { x \oplus (m-1) \mid x \in A } )，且 ( \operatorname{ultra}(A) ) 必含 0。
3. mex-稳定：存在 ( l ) 使得对所有 ( i \geq l )，( m_i = m_l )（( m_i = \operatorname{mex}(A_i) )）。
4. mex-极限：稳定后的 ( m_l )。

算法思路

1. 性质推导：

   • 若 ( p = 2^k )，则 ( A_0 ) 必须包含所有 ( 0 \sim 2^k-1 ) 的数（即 ( n = 2^k )），否则无解。
   • 若 ( p ) 不是 2 的幂，直接无解（输出 0）。
   • 若 ( p = 2^w )（( w < k )），需统计满足条件的集合数，这是本题的核心。

2. 组合计数与 NTT 优化：

   • 预处理组合数 ( C(n, m) )，用于计算元素选择的方案数。
   • 利用 NTT（数论变换）加速复杂的组合计数，处理“集合划分与稳定性”的约束条件。

3. 动态预处理：

   • 对每个可能的 ( w )（( p = 2^w )），预处理满足条件的集合数，存储到 res[k][n] 中，支持快速查询。

代码解析

1. 输入处理与初始化：

   • 读取模数 ( p ) 和测试用例，初始化组合数 ( \text{fac} )（阶乘）和 ( \text{fiv} )（阶乘逆元）。
   • 预处理原根 ( g ) 和 NTT 所需的单位根 ( e[i] )。

2. NTT 加速计数：

   • 函数 INTT 实现数论逆变换，用于将频域结果转换为空域，加速组合计数的合并。
   • 通过递推和 NTT 预处理 res[k][n]，存储 ( k ) 位下选择 ( n ) 个元素且 mex-极限为 ( 2^w ) 的集合数。

3. 查询处理：

   • 对每个测试用例，根据 ( p ) 的形式（是否为 2 的幂、是否等于 ( 2^k ) 等），直接查表或计算结果。

复杂度分析

• 预处理阶段：组合数预处理为 ( O(\text{Lim}) )，NTT 预处理为 ( O(2^T \log 2^T) )（( T = 17 )），总复杂度为 ( O(2^{17} \times 17) )，可接受。
• 查询阶段：每次查询为 ( O(1) )，支持 ( 10^5 ) 组测试用例。

关键结论

本题的核心是利用“2 的幂”的性质缩小问题范围，结合组合数学和 NTT 高效处理集合计数，最终实现对所有测试用例的快速响应。

代码输出：对于每组测试用例，输出满足条件的集合数对 ( p ) 取模的结果。