多项式学习笔记
前言
不要问为啥跟全家桶是分开写的，问就是全家桶实在是太多了/jk
[ZJOI2014] 力
题目链接：[ZJOI2014] 力
题意
给出 \(n\) 个数 \(q_1,q_2, \dots q_n\)，定义
\[F_j~=~\sum_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}~-~\sum_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - j)^2}
\]
\[E_i~=~\frac{F_i}{q_i}
\]
对 \(1 \leq i \leq n\)，求 \(E_i\) 的值。
Solution
对于多项式相关题目，不应当仅仅局限于处理多项式问题上，应当将其看作一个卷积的问题形式进行处理，也就是：
\[C_i = \sum_{j = 1}^{i - 1}A_j · B_{i - j}
\]
对于本题，处理思路就是将现有的问题，转化成一个卷积问题，然后利用 FFT 加速求解，下面开始推式子。
\[E_i~=~\frac{F_i}{q_i} = \sum_{j = 1}^{i - 1} \frac{q_j}{(i - j)^2}~-~\sum_{j = i + 1}^{n} \frac{q_j}{(i - j)^2}
\]
对于 \(\sum_{j = 1}^{i - 1} \frac{q_j}{(i - j)^2}\)，显然是一个卷积的形式，可以通过 FFT 直接求解，提出右侧部分求值。
\[\sum_{j = i + 1}^{n} \frac{q_j}{(i - j)^2} = \sum_{j = 1}^{n - i} \frac{q_{i+j}}{j^2}
\]
下标问题解决了，但是卷积形式还没完全成立，有一个常用的小技巧，翻转数组，记 \(q'\) 为 \(q\) 的翻转reverse，则有
\[\sum_{j = 1}^{n - i} \frac{q'_{n-j-i}}{j^2}
\]
这样的话，右边也变成了卷积的形式，就可以 FFT 对左右部分分别求解，得出答案。
Code
点击查看代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long lld;
const int N = 3e5 + 50;
const double PI = acos (-1.0);
struct Complex {
double x, y;
Complex (register double xx = 0, register double yy = 0) {
x = xx, y = yy;
}
inline Complex operator + (const Complex &a) const {
return Complex (a.x + x, a.y + y);
}
inline Complex operator - (const Complex &a) const {
return Complex (x - a.x, y - a.y);
}
inline Complex operator * (const Complex &a) const {
return Complex (x * a.x - y * a.y, x * a.y + y * a.x);
}
} a[N], b[N], c[N], ans1[N], ans2[N];
inline int read () {
register int x = 0, w = 1;
register char ch = getchar ();
for (; ch < '0' || ch > '9'; ch = getchar ()) if (ch == '-') w = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar ()) x = x * 10 + ch - '0';
return x * w;
}
int n;
int limit = 1;
int l, r[N];
inline void FFT (register Complex * A, register int type) {
for (register int i = 0; i < limit; i ++)
if (i < r[i]) swap (A[i], A[r[i]]);
for (register int mid = 1; mid < limit; mid <<= 1) {
register Complex Wn (cos (PI / mid), type * sin (PI / mid));
for (register int R = mid << 1, j = 0; j < limit; j += R) {
register Complex w (1, 0);
for (register int k = 0; k < mid; k ++, w = w * Wn) {
register Complex x = A[j + k], y = w * A[j + mid + k];
A[j + k] = x + y;
A[mid + j + k] = x - y;
}
}
}
}
int main () {
n = read() - 1;
for (register int i = 0; i <= n; i ++) scanf ("%lf", &a[i].x);
for (register int i = 0; i <= n; i ++) c[n - i].x = a[i].x;
for (register int i = 1; i <= n; i ++) b[i].x = (double)1.0 / (double)i / (double)i;
while (limit <= (n << 1)) limit <<= 1, l ++;
for (register int i = 0; i < limit; i ++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
FFT (a, 1), FFT (b, 1);
for (register int i = 0; i < limit; i ++) ans1[i] = a[i] * b[i];
FFT (ans1, -1);
FFT (c, 1);
for (register int i = 0; i < limit; i ++) ans2[i] = c[i] * b[i];
FFT (ans2, -1);
for (register int i = 0; i < limit; i ++) ans1[i].x /= limit, ans2[i].x /= limit;
for (register int i = 0; i <= n; i ++) printf ("%.3lf\n", ans1[i].x - ans2[n - i].x);
putchar ('\n');
return 0;
}