P7493 旅人1969
LGyxj
·
·
题解
最开始以为是反演，但很快发现并不是。
考虑进行 dp 。
不难想出，有以下转移：
$$f_{k, n} = \sum\limits_{x = 1}^m f_{k - 1, n - x}$$
于是写出它的生成函数
$$g = \sum\limits_{i = 1}^m x^i$$
$$f_k = g^k$$
那么我们要求的就是
$$h_k = \sum\limits_{i = 0}^k f_i$$
显然，这个东西是可以倍增的，即
$$h_{2k} = h_k + f_k * h_k$$
那么求出所有 $h_{2^i}$ 和 $f_{2^i}$，这部分是 $O(n \log k)$ 的。
再对 $k$ 进行二进制数位 dp 即可，不难发现，这部分也是 $O(n \log k)$ 的。
主要代码如下
```cpp
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;
}
```