自动搬运

查看原文

来自洛谷，原作者为

	LGyxj 摆烂是一种态度

搬运于2025-08-24 22:30:23，当前版本为作者最后更新于2023-09-27 16:20:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最开始以为是反演，但很快发现并不是。

考虑进行 dp 。

$f_{k, n}$ 表示走了 $k$ 步，走到第 $n$ 个点。

不难想出，有以下转移：

于是写出它的生成函数

那么我们要求的就是

显然，这个东西是可以倍增的，即

那么求出所有 $h_{2^i}$ 和 $f_{2^i}$，这部分是 $O(n \log k)$ 的。

再对 $k$ 进行二进制数位 dp 即可，不难发现，这部分也是 $O(n \log k)$ 的。

主要代码如下

void solve() {
	for (int i = 0; i < Nn; ++ i) cur[i] = 1;
	for (int i = 1; i <= m; ++ i) g[i] = 1;
	fft(g); memcpy(f[0], g, sizeof g);
	memcpy(h[0], g, sizeof g);
	for (int i = 1; i < 14; ++ i) {
		for (int j = 0; j < Nn; ++ j) 
			f[i][j] = 1ll * f[i - 1][j] * f[i - 1][j] % mod;
		for (int j = 0; j < Nn; ++ j) 
			h[i][j] = (h[i - 1][j] + 1ll * h[i - 1][j] * f[i - 1][j]) % mod;
	}
	for (int i = 14; ~i; -- i) {
		if (k >> i & 1) {
			for (int j = 0; j < Nn; ++ j) 
				qx[j] = (qx[j] + 1ll * cur[j] * h[i][j]) % mod;
			for (int j = 0; j < Nn; ++ j) cur[j] = 1ll * cur[j] * f[i][j] % mod;
		}
	}
	fft(qx, 0); qx[0] = 1;
}