题解：格子覆盖计数问题

问题分析

题目要求计算 $M$ 个人在 $N$ 个格子上跳跃，每个格子至少被一个人踩过的方案数。每个人从第 $1$ 个格子出发，每次可以跳 $1$ 格（方法数 $p$）或 $2$ 格（方法数 $q$），超出第 $N$ 个格子则停止。

核心思路

1. 问题转化

使用容斥原理将"每个格子至少被覆盖一次"转化为"某些格子没有被覆盖"的补集问题。通过生成函数方法统一处理。

2. 生成函数方法

• 构建关于格子覆盖状态的生成函数
• 利用多项式运算处理组合关系
• 通过快速数论变换(NTT)优化多项式乘法

3. 线性递推求解

对于大规模 $N$（达到 $10^9$），使用线性递推的快速算法：

• 利用矩阵快速幂思想
• 通过多项式取模优化
• 在 $O(M \log M \log N)$ 时间内求解

关键技术

1. 特征根分解

跳跃过程对应特征方程 $x^2 - px - q = 0$，得到两个特征根：

$$A = \frac{p - \sqrt{p^2 + 4q}}{2}, \quad B = \frac{p + \sqrt{p^2 + 4q}}{2} $$

在模 $998244353$ 下处理平方根，使用扩域技巧。

2. 多项式卷积

• 构建关于 $A^i B^{M-i}$ 的多项式
• 使用分治NTT计算多项式乘积
• 处理大规模多项式运算

3. 线性递推优化

对于递推式：

$$f_n = a_1 f_{n-1} + a_2 f_{n-2} + \cdots + a_k f_{n-k} $$

使用多项式取模和快速幂，在 $O(k \log k \log n)$ 时间内计算 $f_n$。

算法流程

1. 预处理特征根：计算 $A, B$ 在模意义下的表示
2. 构建生成函数：通过分治NTT计算容斥多项式
3. 计算初始值：处理前 $M+1$ 项的值
4. 线性递推求解：使用快速算法计算第 $N$ 项
5. 输出结果：取模后输出最终答案

复杂度分析

• 时间复杂度：$O(M \log^2 M + M \log M \log N)$
• 空间复杂度：$O(M)$

算法总结

本题的解法展示了如何将组合计数问题转化为多项式运算和线性递推问题，主要亮点包括：

1. 容斥原理应用：巧妙地将覆盖问题转化为补集计数
2. 生成函数技巧：利用多项式统一处理复杂的组合关系
3. 扩域处理：在模意义下处理特征根和平方根运算
4. 线性递推优化：针对大规模 $N$ 的高效算法设计
5. NTT加速：通过快速数论变换优化多项式运算