题解

问题分析

题目要求计算具有 ( n ) 个叶子的“铁”树数量，其中非叶节点的孩子数必须属于给定集合 ( D )。核心挑战在于 ( n ) 可高达 ( 10^{18} )，直接递推或枚举不可行，需结合数论和生成函数的高级技巧。

核心思路

1. 生成函数建模：

   • 定义生成函数 ( F(x) = \sum_{n \ge 1} f(n) x^n )，其中 ( f(n) ) 为 ( n ) 个叶子的“铁”树数量。
   • 根据“铁”树定义，生成函数满足方程：( F(x) = x + \sum_{d \in D} F(x)^d )。
     • 解释：( x ) 对应单个叶子节点；( \sum_{d \in D} F(x)^d ) 对应非叶节点（有 ( d \in D ) 个孩子，每个孩子为一棵子树）。

2. 模运算与分解：

   • 模数 ( M \le 50 )，可分解为质数幂的乘积（如 ( M = p_1^{e_1} p_2^{e_2} \cdots )）。
   • 利用中国剩余定理（CRT），分别计算模每个质数幂的结果，再合并得到最终答案。

3. 大指数处理：

   • 对于质数幂模 ( p^e )，利用生成函数的性质和多项式同余化简计算。例如，通过多项式的幂运算性质 ( f(x)^{p^k} \equiv f(x^p)^{p^{k-1}} \mod p^e ) 降低指数规模。
   • 递归分解指数 ( n )，结合多项式乘法和快速幂，高效求解生成函数系数。

代码解析

1. 模运算框架：

   • 定义 ModInt 结构体，支持模算术运算（加减乘除、幂运算），并通过 Barrett 优化加速乘法取模。

2. 生成函数与多项式：

   • 实现多项式乘法，用于生成函数的卷积运算。
   • 预处理多项式幂 ( f[i][j] )，表示特定指数下的生成函数多项式，用于快速组合大指数。

3. 质数幂分解与CRT：

   • 将模数 ( M ) 分解为质数幂 ( p^e )，对每个质数幂单独计算结果。
   • 对每个 ( n )，通过递归分解指数和多项式运算，得到模 ( p^e ) 的结果。
   • 利用中国剩余定理合并各质数幂的结果，得到模 ( M ) 的最终答案。

4. 大指数递归计算：

   • 对于 ( n \le 10^{18} )，通过分解指数为 ( p ) 进制，结合预处理的多项式幂，逐步降低问题规模，最终求解生成函数中 ( x^{n-1} ) 的系数（对应 ( f(n) )）。

总结

该解法通过生成函数建模“铁”树计数问题，结合模算术分解、多项式运算和中国剩余定理，高效处理了 ( n \le 10^{18} ) 的极端输入。核心是利用数论性质将大指数问题分解为可处理的子问题，再通过多项式运算和CRT合并结果，时间复杂度主要依赖于模数分解后的质数幂个数和多项式运算规模，适用于题目给定的约束条件。