# Nemlit 的博客

By a konjac

### 多项式学习笔记

posted on 2019-10-07 20:52:04 | under 未分类 |

## $FFT$

$$c(k) = \sum_{i+j = k}a(i)*b(j)$$

## $DFT:$

$$(a + b*i) +(c+d*i) = (a+c)+(b+d)*i$$ $$(a + b*i) -(c+d*i) = (a-c)+(b-d)*i$$ $$(a + b*i) *(c+d*i) = (a*c - b*d)+(a*d+b*d)*i$$

$$F(w_n^x) = F1(w_n^{2*x})+w_n^x*F2(w_n^{2*x})$$

$$w_{2n}^{2x} = w_{n}^x$$

$$w_{n}^{x+\frac{n}{2}} = -w_{n}^x$$

$$F(w_n^{x+\frac{n}{2}}) = F1((w_{n}^{x+\frac{n}{2}})^2)+w_n^{x+\frac{n}{2}}*F2((w_{n}^{{x+\frac{n}{2}}})^2)$$ 由于第二条性质 $$F(w_n^{x+\frac{n}{2}}) = F1((-w_{n}^x)^2)-w_n^{x}*F2((-w_{n}^{x})^2)$$ $$F(w_n^x) = F1(w_{\frac{n}{2}}^{x})-w_n^x*F2(w_{\frac{n}{2}}^{x})$$

## $IDFT$

$$A_0*(w_n^0)^0+A_1*(w_n^0)^1+A_2*(w_n^0)^2+……+A_n*(w_n^0)^2$$ $$A_0*(w_n^1)^0+A_1*(w_n^1)^1+A_2*(w_n^1)^2+……+A_n*(w_n^1)^2$$ $$……$$ $$A_0*(w_n^{n - 1})^0+A_1*(w_n^{n - 1})^1+A_2*(w_n^{n - 1})^2+……+A_n*(w_n^{n - 1})^2$$

$s*w_n^k = \sum_{j=1}^{n}(w_n^k)^j =s-1+(w_n^k)^n = s$

## $Code:$

struct node {
D x, y;
}a[maxn], b[maxn];
il node operator + (node a, node b) {return (node){a.x + b.x, a.y + b.y};}
il node operator - (node a, node b) {return (node){a.x - b.x, a.y - b.y};}
il node operator * (node a, node b) {return (node){a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};}
int n, m, lim;
il void FFT(node *x, int f, int len) {
if(len == 1) return;
node f1[len >> 1], f2[len >> 1];
for(re int i = 0; i < len; i += 2) f1[i / 2] = x[i], f2[i / 2] = x[i + 1];
FFT(f1, f, len >> 1), FFT(f2, f, len >> 1);
node w = (node){1, 0}, base = (node){cos(2.0 * pi / len), f * sin(2.0 * pi / len)};
for(re int i = 0; i < (len >> 1); ++ i, w = w * base) {
x[i] = f1[i] + w * f2[i], x[i + (len >> 1)] = f1[i] - w * f2[i];
}
}
int main() {
rep(i, 0, n) a[i].x = read();
rep(i, 0, m) b[i].x = read();
while((1 << lim) <= n + m) ++ lim;
FFT(a, 1, (1 << lim)), FFT(b, 1, (1 << lim));
rep(i, 0, (1 << lim)) a[i] = a[i] * b[i];
FFT(a, -1, (1 << lim));
rep(i, 0, n + m) printf("%d ", (int)(a[i].x / (1 << lim) + 0.5));
return 0;
}

## $Code:$

il void FFT(node *x, int f, int len) {
rep(i, 0, len - 1) if(i < r[i]) swap(x[i], x[r[i]]);
for(int mid = 1; mid < len; mid <<= 1) {
node base = (node){cos(pi / mid), f * sin(pi / mid)};
for(re int p = mid * 2, j = 0; j < len; j += p) {
node w = (node){1, 0};
for(re int k = 0; k < mid; ++ k, w = w * base) {
node a = x[j + k], b = w * x[j + k + mid];
x[j + k] = a + b, x[j + k + mid] = a - b;
}
}
}
}
rep(i, 0, (1 << lim)) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lim - 1));

## $Code:$

#define mod 998244353
#define invG 332748118
#define G 3
#define maxn 10000006
int n, m, a[maxn], b[maxn], l, lim = 1, r[maxn];
il int qpow(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = 1ll * r * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return r;
}
il void NTT(int *x, int f, int len) {
rep(i, 0, len) if(i < r[i]) swap(x[i], x[r[i]]);
for(re int mid = 1; mid < len; mid <<= 1) {
int base = qpow((f == 1) ? G : invG, (mod - 1) / (mid << 1));
for(re int p = mid * 2, j = 0; j < len; j += p) {
for(re int k = 0, w = 1; k < mid; ++ k, w = 1ll * w * base % mod) {
int a = x[j + k], b = 1ll * w * x[j + k + mid] % mod;
x[j + k] = (a + b) % mod, x[j + k + mid] = (a - b + mod) % mod;
}
}
}
}
signed main() {
rep(i, 0, n) a[i] = read();
rep(i, 0, m) b[i] = read();
while(lim <= (n + m)) ++ l, lim <<= 1;
rep(i, 0, lim) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
NTT(a, 1, lim), NTT(b, 1, lim);
rep(i, 0, lim) a[i] = 1ll * a[i] * b[i] % mod;
NTT(a, -1, lim);
int inv = qpow(lim, mod - 2);
rep(i, 0, n + m) printf("%d ", (1ll * a[i] * inv) % mod);
return 0;
}

### 分治 $FFT$

$f(x)=\dfrac{1}{1-g(x)}$ ，求逆即可

### 一些简单的生成函数

#### 广义组合数：

$\dbinom{n}{m}=\dfrac{\prod_{i=n-m+1}^ni}{m!}$ ，所以组合数我们可以拓展到任意实数的情况

#### 广义二项式定理

$(x+y)^{n}=\sum_{i=0}^{inf}\binom{n}{i}*x^i*y^{n-i}$

## 例题：

### 4.染色

$f_i=\dfrac{n!}{(S!)^i*(n-S*i)!}$

$g_i=\sum_{j=i}^n(-1)^{j-i}\dbinom{j}{i}f_j=\sum_{j=i}^n(-1)^{j-i}*\dfrac{j!}{i!(j-i)!}=\dfrac{(-1)^{j-i}}{(j-i)!}*(j!*f_j)*\dfrac{1}{i!}$