题解 CF923E 【Perpetual Subtraction】
x义x
·
·
题解
题目大意.
求 A^mP，其中 P 给定，A 是一个线性变换：
p_i\leftarrow \sum_{j\ge i}\dfrac{p_j}{j+1}
下标范围均为 0\sim n。
**题解.**
~~草，好像和官方题解撞了~~
既然给出了一个线性变换，还要我们求高次幂，不难想到[**对角化**](https://xyix.github.io/posts/?page=0&postname=linear-algebra)。
那没啥好说的，大力解吧。具体找出的特征向量为：编号为 $i\in[0\sim n]$ 的特征向量的第 $j\in[0\sim n]$ 维是
$$
(-1)^{i+j}{i\choose j}
$$
记 $F$ 是把第 $i$ 个 $A$ 的特征向量作为第 $i$ 列构成的矩阵，则我们就得到
$$
A^m=F(F^{-1}AF)^mF^{-1}
$$
大力手算可以得出：
- $F^{-1}$ 的 $i$ 列 $j$ 行 为 ${i\choose j}$。
- $F^{-1}AF$ 是对角矩阵，其第 $i$ 列 $i$ 行为 $\dfrac{1}{i+1}$。
乘以 $F$ 和 $F^{-1}$ 显然都可以使用 NTT 优化。
```cpp
int main() {
init();
scanf("%d%lld", &n, &m); n++; F.resize(n); G.resize(n);
for(int i = 0; i < n; i++) scanf("%d", &F[i].x), F[i] *= fac[i];
F.reverse();
for(int i = 0; i < n; i++) G[i] = ifac[i];
F = Conv(F, G, n << 1); F.resize(n);
F.reverse();
for(int i = 0; i < n; i++) F[i] *= qpow(inv[i + 1], m % (p - 1)), F[i] = i & 1 ? -F[i] : F[i];
F.reverse();
F = Conv(F, G, n << 1); F.resize(n);
F.reverse();
for(int i = 0; i < n; i++) F[i] *= ifac[i], F[i] = i & 1 ? -F[i] : F[i], printf("%d ", F[i].x);
}
```