题解：P14461 【MX-S10-T2】『FeOI-4』青年晚报
liruixiong0101
·
·
题解
用一点算子理论的知识公式化的求解。
用求导算子书写原关系式为：
\begin{aligned}
F_i&=(1+\frac{\text d}{\text dx})G_{i-1} \\
G_i&=(1-\frac{\text d}{\text dx})F_{i-1}
\end{aligned}
那么就有：
\begin{aligned}
F_i&=(1+\frac{\text d}{\text dx})G_{i-1} \\
&=(1+\frac{\text d}{\text dx})(1-\frac{\text d}{\text dx})F_{i-2} \\
&=(1-\frac{\text d^2}{\text dx^2})F_{i-2}
\end{aligned}
我们显然还可以得到：
$$
F_i=(1-\frac{\text d^2}{\text dx^2})^kF_{i-2k}
$$
我们不妨设 $n$ 为偶数，若 $n$ 为奇数则求出 $F_1,G_1$，从它们开始就行了。
我们令 $k=\frac n2,i=n$，则有：
$$
F_n=(1-\frac{\text d^2}{\text dx^2})^{\frac n2}F_0
$$
用二项式定理展开得到：
$$
\begin{aligned}
F_n&=(1-\frac{\text d^2}{\text dx^2})^{\frac n2}F_0 \\
&=\sum_{i=0}^{\frac n2}{\frac n2\choose i}(-1)^i\frac{\text d^{2i}}{\text dx^{2i}}F_0
\end{aligned}
$$
注意到对于一个多项式 $f$，求 $\deg f+1$ 次导数就会变成 $0$（其中 $\deg f$ 为多项式 $f$ 的次数）。
所以当 $i>\lfloor\frac m2\rfloor$ 时，$\frac{\text d^{2i}}{\text dx^{2i}}F_0=0$。
那么这个求和范围的上界就可以从 $\frac n2$ 变成 $\lfloor\frac m2\rfloor$，递推求出 ${\frac n2\choose i}$ 和 $\frac{\text d^{2i}}{\text dx^{2i}}F_0$ 就可以在 $O(m^2)$ 的时间内求出 $F_n$。
$G_n$ 同理。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int kM = 1e9 + 7;
int n, m, k;
vector<int> f, g, F, G;
int Fpow(int a, int b, int p, int r = 1) {
for (; b; a = 1LL * a * a % p, b >>= 1) {
if (b & 1) r = 1LL * r * a % p;
}
return r % p;
}
vector<int> Deriv(vector<int> f) {
vector<int> g(f.size());
for (int i = 0; i < f.size() - 1; i++) {
g[i] = 1LL * f[i + 1] * (i + 1) % kM;
}
return g;
}
vector<int> operator+(vector<int> f, vector<int> g) {
vector<int> h(f.size());
for (int i = 0; i < h.size(); i++) {
h[i] = (f[i] + g[i]) % kM;
}
return h;
}
vector<int> operator*(int x, vector<int> f) {
x = (x % kM + kM) % kM;
vector<int> g(f.size());
for (int i = 0; i < g.size(); i++) {
g[i] = 1LL * x * f[i] % kM;
}
return g;
}
int main() {
cin >> n >> m;
f.resize(m + 1);
g.resize(m + 1);
for (int i = 0; i <= m; i++) {
cin >> f[i];
}
for (int i = 0; i <= m; i++) {
cin >> g[i];
}
if (n % 2) {
F = f, G = g;
f = G + Deriv(G);
g = F + -1 * Deriv(F);
}
F = f, G = g;
k = n / 2;
f = vector<int>(m + 1);
g = vector<int>(m + 1);
for (int i = 0, binom = 1, o = 1; 2 * i <= m && i <= k; i++) {
f = f + o * binom * F;
g = g + o * binom * G;
binom = 1LL * binom * (k - i) % kM * Fpow(i + 1, kM - 2, kM) % kM;
o *= -1;
F = Deriv(Deriv(F)), G = Deriv(Deriv(G));
}
for (int i = 0; i <= m; i++) {
cout << f[i] << " \n"[i == m];
}
for (int i = 0; i <= m; i++) {
cout << g[i] << " \n"[i == m];
}
return 0;
}
```