### 简单的普及组计数

有一初始为空的字符串 $S$, 每次可以在某一位置加入连续的 $k$ 个相同字符, 求进行 $n$ 次操作能得到的 $S$ 的个数, $|\Sigma|=m$. $n,k\le 10^9,m,mod\le 10^5$, 模数为质数.

考虑所有操作形成一个类树状结构, 即对于某一点, 其代表一次操作, 对于该操作形成的 $k-1$ 个空隙, 可以连接任意多的子节点. 设 $[x^i]F(x)$ 为进行树大小为 $i$, 根颜色未确定, 的方案数. 有 $F(x)=\frac{x}{(1-(m-1)F(x))^{k-1}}$, 答案为 $[x^n]\frac{1}{1-mF(x)}$. 

考虑拉格朗日反演, 记 $F(x)$ 的复合逆为 $F'(x)$, 有 $F(F'(x))=\frac{F'(x)}{(1-(m-1)x)^{k-1}}=x$, 即 $F'(x)=x(1-(m-1)x)^{k-1}$. 设 $G(x)=\frac{1}{1-mx}$, 进行拉格朗日反演得
$$
[x^n]G(F(x))&=&[x^n]G(x)(F'(x))'(\frac{x}{F'(x)})^{n+1}\\
&=&\frac{1}{1-mx}\cdot (1-(m-1)x)^{k-2}(1-(m-1)kx)\cdot (1-(m-1)x)^{-(k-1)(n+1)}\\
&=&[x^n]H(x)-(m-1)k[x^{n-1}]H(x)\\
$$
其中 $H(x)=\frac{1}{1-mx}\cdot \frac{1}{(1-(m-1)x)^{kn-n+1}}$. 则
$$
[x^p]H(x)&=&[x^p](\sum_i m^ix^i)(\sum_i (m-1)^i\binom{i+kn-n}{kn-n}x^i) \\
&=& \sum_{i\in [0,p]} m^{p-i}(m-1)^i \binom{i+kn-n}{kn-n} \\
$$
设 $f(a,b,c)=\sum_{i\in [0,a]}\binom{i}{b}c^i$, 则 $[x^p]H(x)=f(kn-n+p,kn-n,\frac{m-1}m)\frac{m^{kn-n+p}}{(m-1)^{kn-n}}$. 注意到模数不大, 考j虑 Lucas 定理和费马小定理:
$$
f(a,b,c)&=&\sum_{i\in [0,a]} \binom{i\bmod mod}{b\bmod mod}\binom{\lfloor i/mod\rfloor}{\lfloor b/mod \rfloor} c^{i\bmod mod}c^{\lfloor i/mod\rfloor} \\
&=&\sum_{j\in [0,mod-1]}\binom{j}{b\bmod mod}c^{j}(\sum_{i'\in [0,\lfloor (a-j)/mod\rfloor]} \binom{i'}{\lfloor b/mod \rfloor}c^{i'})\\
&=&\sum_{j\in [0,mod-1]}\binom{j}{b\bmod mod}c^{j}\cdot f(\lfloor (a-j)/mod\rfloor,\lfloor b/mod \rfloor,c) \\
$$
记忆化搜索即可. 时间复杂度分析: $a$ 每次变成 $\{\lfloor a/mod\rfloor,\lfloor a/mod\rfloor-1\}$, 再变成 $\{\lfloor a/mod^2\rfloor,\lfloor a/mod^2\rfloor-1,\lfloor a/mod^2\rfloor-2\}$, 其中 $\lfloor a/mod^2\rfloor-2$ 出现概率不大. 通过打表发现, 若 $a_0=10^{18}$, 当 $mod=2$ 时, $a$ 个数最多, 为 $172$. 可以接受.

时间复杂度 $O((m+mod)\log_{mod}(nk))$.