题解：多项式模 2 幂次展开与子串匹配

问题转化

多项式 ( f(x) ) 在模 2 意义下进行幂运算，求幂次展开后的 01 串中某子串的匹配次数。设：

• ( N = nm + 1 )，为最终字符串长度
• 字符串下标从 1 到 ( N )，对应 ( x^{nm}, x^{nm-1}, \dots, x^0 ) 的系数

核心思路

1. 系数的计算

设 ( f(x) = \sum_{i=0}^n a_i x^i )（( a_i \in {0,1} )），那么： [ f(x)^m = \sum_{k_0+\cdots+k_n = m} \binom{m}{k_0,\dots,k_n} \left( \prod_{i=0}^n a_i^{k_i} \right) x^{k_0\cdot 0 + k_1\cdot 1 + \cdots + k_n\cdot n} ] 由于在模 2 下运算，系数非 0 即 1，而： [ \binom{m}{k_0,\dots,k_n} \bmod 2 = 1 \text{ 当且仅当在二进制加法中无进位} ] 这与 Lucas 定理相关：系数 ( c_j )（( x^j ) 的系数）在模 2 下为： [ c_j = \sum_{\substack{k_0+\cdots+k_n = m \ \sum i k_i = j}} \left[ \binom{m}{k_0,\dots,k_n} \bmod 2 \cdot \prod_{i=0}^n a_i^{k_i} \bmod 2 \right] \ (\text{mod } 2) ] 即模 2 加法等价于异或。

---

2. 转为多重集划分问题

由于模 2 下只有奇偶性，用 Lucas 定理得： [ \binom{m}{k_0,\dots,k_n} \bmod 2 = 1 \ \text{当且仅当在二进制下，对每一位，所有 } k_i \text{ 在该位的和等于 } m \text{ 的这一位} ] 更简便的视角是：将幂次乘法看作 ( m ) 个 ( f(x) ) 相乘，选择每个 ( f(x) ) 中的一个单项（其指数），然后求和得到总指数，系数为这些单项系数的乘积（模 2）。

于是 ( c_j ) 是：考虑所有长度为 ( m ) 的序列 ((d_1,\dots,d_m))，其中 ( d_t \in { i \mid a_i = 1 } )（即 ( f ) 中系数为 1 的项指数集合），若有 (\sum_{t=1}^m d_t = j)，则贡献 1 的系数（模 2 相加）。

所以 ( c_j ) 是：从集合 ( S = { i \mid a_i = 1 } ) 中允许重复地选 ( m ) 个数，使得它们之和为 ( j ) 的方案数的奇偶性。

---

3. 与组合数的关系

设 ( S = {e_1, e_2, \dots, e_p} ) 为 ( f(x) ) 中系数为 1 的指数集合（( p ) 为系数为 1 的项数）。
则 ( c_j ) 是方程 [ x_1 + x_2 + \cdots + x_m = j,\quad x_t \in S ] 的解的个数的奇偶性。

这在模 2 下等于： [ c_j = \left( \sum_{(r_1,\dots,r_p) \geq 0,\ \sum r_i=m,\ \sum r_i e_i = j} \binom{m}{r_1,\dots,r_p} \right) \bmod 2 ] 利用 Lucas 定理模 2，该组合数为奇当且仅当在二进制下，对每一位，所有 ( r_i ) 的这一位之和等于 ( m ) 的这一位。

---

4. 二进制自动机（关键转化）

我们可以将 ( j ) 的二进制表示与 ( m ) 的二进制表示联系起来。
设 ( m ) 的二进制为 ( (b_{B-1}\dots b_0)_2 )。
那么对每个 ( j )，我们可以判断 ( c_j ) 是否为 1 的方法：

构造状态自动机：考虑 ( m ) 的二进制每一位，我们需要分配该位的“1”的个数到 ( r_i ) 上，同时要满足低位到高位的进位。

已知技巧（Kummer 定理推广）：组合数 (\binom{m}{r_1,\dots,r_p}) 模 2 为 1，当且仅当在二进制加法 ( r_1 + \dots + r_p = m ) 时不发生进位（在每一位上直接相等）。

因此条件是在二进制每一位 ( \ell ) 上： [ \sum_{i=1}^p r_i^{(\ell)} = b_\ell ] 其中 ( r_i^{(\ell)} ) 是 ( r_i ) 二进制第 ( \ell ) 位，且 ( r_i^{(\ell)} \in {0,1} )。

---

5. 生成函数与系数递推

更实用的是用 DP 计算某个 ( j ) 的 ( c_j )。
设 ( E = {e_1,\dots,e_p} )，定义生成函数： [ F(y) = \sum_{i \in E} y^i ] 那么在模 2 下，( c_j ) 是 ( F(y)^m ) 中 ( y^j ) 的系数的奇偶性。

利用模 2 运算的性质，以及二进制幂次快速乘法： [ F(y)^{2^k} \equiv F(y^{2^k}) \pmod{2} ] 因为 ( (u+v)^2 \equiv u^2 + v^2 \ (\text{mod } 2) )，推广得 ( G(y)^2 \equiv G(y^2) )。

所以将 ( m ) 二进制分解： [ m = \sum_{k=0}^{B-1} m_k 2^k,\quad m_k \in {0,1} ] 那么： [ F(y)^m = \prod_{k: m_k=1} F(y^{2^k})^{2^{k}} \cdot (\text{注意这里实际是直接做}) ] 更准确写法：设 ( P_0(y) = F(y) )，
( P_{k+1}(y) = P_k(y) \cdot P_k(y^{2^k}) \ (\text{mod } 2, \text{ 且合并同类项时模 2}) ) 并不完全对，应直接用重复平方法。

由于是模 2，有： [ F(y)^{2^k} = F(y^{2^k}) ] 所以： [ F(y)^m = \prod_{k: m_k=1} F(y^{2^k}) ] 令 ( m ) 的二进制中为 1 的位是 ( k_1, k_2, \dots, k_q )（从小到大），则： [ F(y)^m = F(y^{2^{k_1}}) \cdot F(y^{2^{k_2}}) \cdots F(y^{2^{k_q}}) \ (\text{模 2 乘法}) ]

---

6. 多项式乘法模 2

模 2 乘法就是多项式的系数模 2 卷积。设： [ A^{(r)}(y) = F(y^{2^{k_r}}) = \sum_{i \in E} y^{i \cdot 2^{k_r}} ] 那么初始时 ( A^{(1)}(y) ) 只有 ( p ) 个非零项，然后依次卷积（模 2）。

每次卷积 ( C(y) = A(y) * B(y) ) 是系数模 2 加法（异或），非零项数量可能增长，但若我们只需要计算特定区间的系数，可以只保留指数在某个范围内的项。

---

7. 区间匹配问题

给定 ( L, R ) 和模式串 ( t )（长度 ( K )），要在 ( s[L,R] ) 中找到 ( t ) 出现次数，即： [ \text{满足 } L \le pos \le R-K+1 \text{ 且 } c_{N-pos}, c_{N-pos-1}, \dots, c_{N-pos-K+1} = t_0 t_1 \dots t_{K-1} ] 注意：字符串 ( s ) 的第 ( pos ) 个字符是 ( c_{N-pos} )，因为 ( s[1] = c_{N-1} = x^{nm} ) 的系数，( s[N] = c_0 = x^0 ) 的系数。

我们需要对每个 ( pos ) 判断 ( K ) 个连续的系数是否与 ( t ) 匹配。直接做需要能快速求出任意连续 ( K ) 个系数。

---

8. 针对不同数据范围的策略

情况 1（( n \le 18, m \le 500 )）：
直接计算所有系数 ( c_0,\dots,c_{nm} )（长度最多约 9000），然后直接匹配。

情况 2（( n ) 大，( m ) 大，但 ( R-L \le 10^4 )）：
只需计算指数在某个范围内的系数。我们通过卷积法计算 ( F(y)^m ) 时，只保留指数在 ([N-R, N-L+K]) 范围内的系数，然后匹配。

情况 3（( L=1, R=N ) 全长）：
此时需在整个 ( c ) 上匹配。可用 FFT 加速卷积（但模 2 需用 bitset 或布尔卷积），但 ( K ) 小时可直接暴力匹配，( K ) 大时用 KMP。

情况 4（一般情况）：
结合卷积限制区间 + KMP 匹配。

---

9. 算法步骤

1. 读入 ( f ) 得到非零指数集合 ( E )。
2. 根据 ( m ) 的二进制分解，得到 ( q ) 个多项式 ( A^{(r)}(y) = \sum_{i \in E} y^{i\cdot 2^{k_r}} )。
3. 依次卷积这些多项式（模 2），但在过程中只保留指数在所需区间内的项（因为多项式稀疏，可用哈希表存非零项，模 2 加法即异或）。
4. 最终得到在区间 ([N-R, N-L+K-1]) 内的系数数组。
5. 将系数转为字符串（高位到低位），用 KMP 在子串 ( s[L,R] ) 中匹配 ( t )。
6. 输出匹配次数。

---

10. 复杂度分析

• 卷积部分：最多 ( O(\log m) ) 次乘法，每次乘法非零项数不超过 ( O(p \cdot 2^{\text{已合并次数}}) )，但通过区间限制可控制在 ( O(\text{区间长度} + p\log m) )。
• 匹配部分：( O(R-L + K) )。
• 对于大数据，该方法是可行的。

---

这样我们就得到了一个可以处理所有数据范围的算法框架。实际实现时需根据数据范围选择具体的卷积和匹配策略。