多项式基础

##一、FFT
n次单位根：
$$w^k_n = e^{\frac{2\pi i}{n}} = cos{\frac{2\pi k}{n}+sin{\frac{2\pi k}{n}i}}$$
可以证明：
$$(w^k_n)^n = 1$$

####1、从系数到点值
对于每一个$w^k_n$求出点值。
我们考虑把它化简。
$$F(w^k_n)=\sum^{n-1}_{i=0}a_i\cdot w^{ki}_n
=\sum^{n/2-1}_{i=0}a_{2i}\cdot w^{2ki}_n
+a_{2i+1}\cdot w^{(2i+1)k}_n
\\ =\sum^{n/2-1}_{i=0}a_{2i}\cdot w^{2ki}_n
+w^k_n\cdot a_{2i+1}\cdot w^{2ki}_n
\\ =\sum^{n/2-1}_{i=0}a_{2i}\cdot w^{ki}_{n/2}
+w^k_n\cdot a_{2i+1}\cdot w^{ki}_{n/2}$$
这里是分奇偶讨论，并且有$w^{2ki}_{n}=w^{ki}_{n/2}$,之后我们发现两部分可以递归处理。
$$\sum^{n/2-1}_{i=0}a_{2i}\cdot w^{ki}_{n/2}
$$
这个相当于把偶数项提出来成为新的多项式。
递归处理就可以了。

####2、从点值到系数
先考虑刚才的过程，考虑把点值集作为向量$((i, f(i)))$，用矩阵描述转移。我们把第$i$行第$j$列为$w^{ij}_n$的矩阵写作$[w^{ij}_n]$。
那么这个过程的实质是：$$(f[i])[w^{ij}_n]=(i, f(i))$$
我们只要找到矩阵的逆$[w^{ij}_n]^{-1}$就可以做逆变换
而这个矩阵就是
$$\frac{1}{n} [w^{-ij}_n]$$
可以~~打表~~证明对角线上是1，其他位置是0。

*另外，有类似FFT的多项式乘法，复杂度为$O(n^{log_2^3})$,貌似python的多项式乘法就运用了这个方法。

##二、牛顿迭代
求解：$$H(F(x))=0$$
设$F_n(x)$是迭代$n$次的解多项式。
把$H(F_{n+1})$在$F_{n}$处泰勒展开前两项。
$$H(F_{n+1}(x))=H(F_n(x))+H^{'}(F_n(x))(F_{n+1}(x)-F_n(x))$$
而牛顿迭代是这样：
$$F_{n+1}(x)=F_n-\frac{H(F_n(x))}{H^{'}(F_n(x))}$$
因为有条件$$H(F(x))=0$$
这两个公式是等价的。

多项式的其他操作网上已经有很好的博客了，这里放出链接：
[多项式操作](http://blog.miskcoo.com/2015/05/polynomial-inverse)

实数域多项式求逆：
```
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 998244353;

struct Complex {
	double r, i; Complex(){}
	Complex(double rr, double ri) {r = rr, i = ri;}
	Complex operator + (const Complex &A) {return Complex(r + A.r, i + A.i);}
	Complex operator - (const Complex &A) {return Complex(r - A.r, i - A.i);}
	Complex operator * (const Complex &A) {return Complex(r * A.r - i * A.i, r * A.i + i * A.r);}
	Complex operator * (const double &d) {return Complex(r * d, i * d);}
	Complex operator / (const double &d) {return Complex(r / d, i / d);}
};
typedef Complex E;
namespace Poly {
	#define For(i, a, b) for(register int i = a; i <= b; ++i)
	const int maxn = 1e5 + 5;
	const double Pi = acos(-1);
	int RL[maxn << 2], mxp2, N;
	E tmp[maxn << 2], tmp2[maxn << 2], tmp3[maxn << 2];
	void init(int n) {
		for(N = 1, mxp2 = 0; N < n; N <<= 1, ++mxp2);
		for(register int i = 1; i <= N; ++i)
			RL[i] = ((RL[i >> 1] >> 1) | ((i & 1) << mxp2 - 1));
	}
	void FFT(E * A, int type) {
		for(register int i = 0; i < N; ++i) 
			if(i < RL[i]) swap(A[i], A[RL[i]]);
		for(register int i = 1; i < N; i <<= 1) {
			E Wn(cos(Pi / i), sin(type * Pi / i));
			for(register int j = 0, p = i << 1; j < N; j += p) {
				E w(1, 0);
				for(register int k = 0; k < i; ++k, w = w * Wn) {
					E x = A[j + k], y = w * A[j + k + i];
					A[j + k] = x + y, A[j + k + i] = x - y;
				}
			}
		}
	}
	void mul(E * A, E * B, int n, int m) {
		init(n + m);
		FFT(A, 1), FFT(B, 1);
		for(register int i = 0; i <= N; ++i)
			A[i] = A[i] * B[i];
		FFT(A, -1);
		for(register int i = 0; i <= N; ++i)
			A[i] = A[i] / N;
	}
	void GetK(E * A, E * B, int k) {
		for(register int i = 0; i <= k; ++i)
			A[i] = B[i];
	}
	void inv(E * A, int n) {
		memset(tmp, 0, sizeof(tmp));
		memset(tmp2, 0, sizeof(tmp2));
		memset(tmp3, 0, sizeof(tmp3));
		tmp[0].r = 1.0 / A[0].r;
		for(register int l = 2; l < n * 2; l <<= 1) {
			memset(tmp2, 0, sizeof(E) * (l + 3));
			for(register int j = 0; j < l; ++j)
				tmp3[j] = tmp[j] * 2;
			GetK(tmp2, A, l), init(l * 3);
			FFT(tmp, 1), FFT(tmp2, 1);
			for(register int i = 0; i <= N; ++i)
				tmp[i] = tmp[i] * tmp[i] * tmp2[i];
			FFT(tmp, -1);
			for(register int i = 0; i <= l; ++i)
				tmp[i] = E(tmp3[i].r - round(tmp[i].r / N), 0);
			for(register int i = l; i <= N; ++i)
				tmp[i] = E(0, 0);
		}
	}
}

int n, a, b;
E A[maxn << 1], B[maxn << 1];
int main() {
	scanf("%d", &n);
	for(register int i = 0; i < n; ++i)
		scanf("%lf", &A[i].r);
	Poly::inv(A, n);
	for(register int i = 0; i < n; ++i)
		printf("%lf ", Poly::tmp[i].r);
	return 0;
}
```

模意义下多项式全家：
```
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 998244353, G = 3;
LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}
namespace Poly {
    #define For(i, a, b) for(register int i = a; i <= b; ++i)
    const int maxn = 1e5 + 5;
    int RL[maxn * 4], mxp2, N;
    int tmp[maxn * 4], tmp2[maxn * 4], tmp3[maxn * 4];
    void init(int n) {
        for(N = 1, mxp2 = 0; N < n; N <<= 1, ++mxp2);
        for(register int i = 1; i <= N; ++i)
            RL[i] = ((RL[i >> 1] >> 1) | ((i & 1) << mxp2 - 1));
    }
    void NTT(int * A, int type) {
        for(register int i = 0; i < N; ++i) 
            if(i < RL[i]) swap(A[i], A[RL[i]]);
        for(register int i = 1; i < N; i <<= 1) {
            LL Wn = fpow(G, (mod - 1) / (i << 1));
            if(type == -1) Wn = fpow(Wn, mod - 2);
            for(register int j = 0, p = i << 1; j < N; j += p) {
                LL w = 1;
                for(register int k = 0; k < i; ++k, w = w * Wn % mod) {
                    int x = A[j + k], y = w * A[j + k + i] % mod;
                    A[j + k] = (x + y) % mod, A[j + k + i] = (x - y) % mod;
                }
            }
        }
    }
    void mul(int * A, int * B, int n, int m) {
        init(n + m);
        NTT(A, 1), NTT(B, 1);
        for(register int i = 0; i <= N; ++i)
            A[i] = 1ll * A[i] * B[i] % mod;
        NTT(A, -1);
        int inv = fpow(N, mod - 2);
        for(register int i = 0; i <= N; ++i)
            A[i] = 1ll * A[i] * inv % mod;
    }
    void GetK(int * A, int * B, int k) {
        for(register int i = 0; i <= k; ++i)
            A[i] = B[i];
    }
    void inv(int * A, int n) {
        memset(tmp, 0, sizeof(int) * (n * 4 + 5));
        memset(tmp2, 0, sizeof(int) * (n * 4 + 5));
        memset(tmp3, 0, sizeof(int) * (n * 4 + 5));
        tmp[0] = fpow(A[0], mod - 2);
        for(register int l = 1; l < n * 2; l <<= 1) {
            for(register int j = 0; j < l; ++j)
                tmp3[j] = tmp[j] * 2 % mod;
            GetK(tmp2, A, l), init(l << 1);
            NTT(tmp, 1), NTT(tmp2, 1);
            for(register int i = 0; i <= N; ++i)
                tmp[i] = (1ll * ((1ll * tmp[i] * tmp[i]) % mod) * tmp2[i]) % mod;
            NTT(tmp, -1);
            int inv = fpow(N, mod - 2);
            for(register int i = 0; i < l; ++i)
                tmp[i] = (tmp3[i] - 1ll * tmp[i] * inv % mod + mod) % mod;
            for(register int i = l; i <= N; ++i)
                tmp[i] = 0;
        }
    }
    void Dif(int * A, int n) {
        for(register int i = 0; i < n - 1; ++i) {
            A[i] = (1ll * A[i + 1] * (i + 1)) % mod;
        }
        A[n - 1] = 0;
    }
    void Itg(int * A, int n) {
        for(register int i = n + 1; i >= 1; --i) {
            A[i] = 1ll * fpow(i, mod - 2) * A[i - 1] % mod;
        }
    }
    void ln(int * A, int n) {
        inv(A, n), Dif(A, n);
        mul(A, tmp, n - 1, n);
        Itg(A, 2 * n - 1);
        for(register int i = n; i < 2 * n; ++i)
            A[i] = 0;
        A[0] = 0;
    }
    int eans[maxn * 4], etmp[maxn * 4];
    void exp(int * A, int n) {
        memset(eans, 0, sizeof(int) * (n * 4 + 3));
        memset(etmp, 0, sizeof(int) * (n * 4 + 3));
        eans[0] = 1;
        for(register int l = 1; l < n * 2; l <<= 1) {
            //memset(etmp, 0, sizeof(int) * (l + 3));
            GetK(etmp, eans, l);
            ln(etmp, l);
            for(register int i = 0; i < l; ++i)
                etmp[i] = (A[i] - etmp[i]) % mod;
            (etmp[0] += 1) %= mod;
            mul(eans, etmp, l, l);
        }
    }
}
int n, m, a, b;
int A[maxn << 1], B[maxn << 1];
signed main() {
	scanf("%d", &n);
	for(register int i = 0; i < n; ++i)
		scanf("%d", &A[i]);
	Poly::inv(A, n);
	for(register int i = 0; i < n; ++i)
		printf("%d ", Poly::tmp[i]);
    return 0;
}
```

线性递推矩阵的特征多项式：
$$f_n=\sum^k_{i=1}a_if_{n-i}$$
$$(-1)^kx^k+\sum^k_{i=1}a_i(-1)^{k-1}x^{k-i}$$

下面是一些题目：
http://cogs.pro:8080/cogs/problem/problem.php?pid=2354
http://cogs.pro:8080/cogs/problem/problem.php?pid=2355
http://cogs.pro:8080/cogs/problem/problem.php?pid=2343
http://cogs.pro:8080/cogs/problem/problem.php?pid=2392
http://cogs.pro:8080/cogs/problem/problem.php?pid=2393
http://cogs.pro:8080/cogs/problem/problem.php?pid=2395
http://cogs.pro:8080/cogs/problem/problem.php?pid=2397
http://cogs.pro:8080/cogs/problem/problem.php?pid=2358
http://cogs.pro:8080/cogs/problem/problem.php?pid=2359
http://cogs.pro:8080/cogs/problem/problem.php?pid=2294

Rockdu's Blog

导航

最近发表

大佬们的友链