Nemlit 的博客

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)$ ,再把两个多项式的点值乘在一起,把新的点值转成多项式 $(IDFT)$ 即可

$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$$

随便说下单位圆/单位根: 现在我们要把圆平分成 $n$ 个,每一个的大小应该是 $cos(2 Π /n), sin(2Π / n)$

步入正题,具体操作长这样: $$F(x) = a_0*x^0+a_1*x^1+a_2*x^2+……+a_n*x^n$$ 设 $F1(x) = a_0*x^0+a_2*x^1+……+a_{n}*x^{\frac{n}{2}}$ , $F2(x) = a_1*x^0+a_3*x^2+……+a_{n - 1}*x^{\frac{n}{2}}$ $$F(x) = F1(x^2)+x*F2(x^2)$$

现在我们只需要知道 $F1(x), F2(x)$ 就可以知道 $F(x)$ 了,于是我们可以递归处理(所以我们需要保证多项式的项数为 $2^x$ )

把单位根带到上述式子里面去,我们有:

$$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) = F1(w_{\frac{n}{2}}^{x})+w_n^x*F2(w_{\frac{n}{2}}^{x})$$

由于我们只知道 $F1(x), F2(x)$ 的 $0-\frac{n}{2}$ 的所有点值要求出 $F(x)$ 的 $0-n$ 的所有点值

分类讨论一下:

如果 $x<\frac{n}{2}$ ,直接用 $F1,F2$ 的值就行

如果 $x≥\frac{n}{2}$ ,不妨设 $x=x+\frac{n}{2}$

$$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$

我们假设我们通过 $DFT$ 求出了点值为 $a_0, a_1……, a_n$ ,最后我们要求出的值为 $A_0, A_1……, A_n$

其实我们只要解一个这样的方程组:

$$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$$

这就是一个矩阵形式了

第一个矩阵是所有的 $(w_n^x)^k$ ,我们计为矩阵V,第二个矩阵为所有的 $A_x$ 计为A,第三个矩阵为所有的 $a_x$ 计为a

于是我们的柿子变成了 $A*V=a$

如果我们知道 $V^{-1}$ ,那么我们有 $a*V^{-1} = A$ ,a即为所求

现在考虑求逆:

我们需要介绍性质三: $\sum_{j = 0}^{n - 1}(w_n^k)^j=[k==0]*n$

证明其实不难,画画图就好了,我们要求的柿子为: $\sum_{j = 0}^{n - 1}(w_n^k)^j$

如果 $k =0$ ,那么原式 $=\sum_{j = 0}^{n - 1} = n$

如果 $k≠0$ ,记 $s=\sum_{j =0}^{n - 1}(w_n^k)^j$

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

因为 $w_n^k≠0$ ,所以 $s=0$

我们令 $V^{-1}(i, j) = (w_n^{-i})^j$

所以 $(V*V^{-1})(i, j)=\sum_{k =0}^{n-1}(w_n^{-i})^k*(w_n^k)^j=\sum_{k = 0}^{n - 1}(w_n^{j -i})^k$

根据性质三,当 $i=j$ 时 $(V*V^{-1})(i, i)=n$ ,否则 $=0$ ,只需要把每一项 $/n$ 即可

然后我们有发现,只需要把 $A$ 看成新的系数,把所有的 $(w_n^j)^k$ 看成 $(w_n^{-j})^k$ ,那么就是一边新的 $DFT$ 了

所以唯一的差别就是单位根前面乘了一个 $-1$ 即可

$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() {
    n = read(), m = read();
    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;
}

讲讲迭代版的 $FFT$

通过打表发现:一个数x再最后一次出现的位置 $r[i]$ 是可以通过公式算出来的: $r[i] = (r[i >> 1] >> 1)\ |\ ((i\ \&\ 1) << (lim - 1))$

然后我们在 $FFT$ 前面把x交换到对应位置,然后用类似上述方法一个个合并即可(我不是懒,是怕东西太多页面卡)

$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));

$NTT:$

大概就是你把原根看成单位根,然后跑 $FFT$ 即可(我不是懒,是怕东西太多页面卡)

$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() {
    n = read(), m = read();
    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;
}

多项式求逆

首先假设原函数为 $G$ , $G*F=1(mod\ x^n)$ ,我们有 $F\%x^1=inv(G_0)$ ,然后,我们思考怎么从 $F\%x^{\frac{n}{2}}$ 推出 $F\%x^n$

令新的多项式为 $H$ ,我们已知 $F*G=1(mod\ x^\frac{n}{2}),H*G=1(mod\ x^n)$ 我们不难发现: $H-F=0(mod\ x^\frac{n}{2})$ ,所以我们有 $(H-F)^2=0(mod\ x^n)$ (这个证明可以把 $(H-F)\%x^\frac{n}{2}$ 为一个 $0-\frac{n}{2}$ 项全为0的多项式,发现平方后前N项全是0)展开后我们有: $H^2+F^2-2*H*F=0(mod\ x^n)$ ,两边同时乘以 $G$ 得, $H+F^2G-2*F=0(mod\ x^n)$

分治 $FFT$

构造 $f(x)=\sum_{i=0}^{inf}x^if_i,\;\;g(x)=\sum_{i=0}^{inf}x^ig_i$ $f(x)*g(x)=\sum_{i=0}^{inf}x^i\sum_{j=0}^{i}f_{i-j}g_j=\sum_{i=1}^{inf}x^if_i=f(x)-1$ (当 $i=0$ 时 $g_i=0$ ) 所以我们有: $f(x)*g(x)+1=f(x)$

$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}$

例题:

0.P3338 [ZJOI2014]力

唯一一道很明显的多项式

1.P3723 [AH2017/HNOI2017]礼物

详见题解

2.P5488 差分与前缀和

详见题解

3.P4173 残缺的字符串

先不考虑通配符,枚举一个结尾元素 $x$ ,如果一个字符串匹配,那么有: $\sum_{i=0}^{m-1}(A_i-B_{x-m+1+i})^2=0$

暴力展开,我们最后得到: $\sum_{i=0}^{m-1}A_i^2+\sum_{i=x-m+1}^xB_i^2=2*\sum_{i=0}^{m-1}A_i*B_{x-m+1+i}$ ,把A数组反转,我们有: $sum_{i=0}^{m-1}A_i^2+\sum_{x-m+1}^xB_i^2=2\sum_{i+j=x}A_i*B_j$

第一项是定值,第二项可以用前缀和,第三项用卷积卷起来,把得到的多项式一位位去匹配即可

现在加上通配符,把通配符看作0,匹配的关系变为, $\sum_{i=0}^{m-1}(A_i-B_{x-m+1+i})^2*A_i*B_{x-m+1+i}=0$

然后同理展开,得到匹配关系变为: $\sum_{i=0}^{m-1}A_i^3*B_{x-m+1+i}+\sum_{i=0}^{m-1}A_iB_{x-m+1+i}^3=2*\sum_{i=0}^{m-1}A_i^2*B_{x-m+1+i}^2$

同理,把A数组反转,我们可以得到: $\sum_{i+j=x}A_i^3*B_j+\sum_{i+j=x}A_iB_j^3=2*\sum_{i+j=x}A_i^2*B_j^2$ ,然后对三个柿子分别做 $FFT$ ,判断即可

4.染色

令 $f_i$ 表示至少 $i$ 个选择 $S$ 个数的方案数, $g_i$ 表示恰好 $i$ 个选择 $S$ 个数的方案

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

证明:把前 $i$ 个数放入集合方案数为: $\dbinom{n}{S}$ ,把第二个i个数放入集合的方案数为 $\dbinom{n-S}{S}$ 以此类推,最后化简即可。

由于剩下 $n-Si$ 个数可以放 $m-i$ 个数,然后我们任意选择i个,所以还需要乘 $\dbinom{m}{i}*(m-i)^{n-Si}$

$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!}$

发现这是一个卷积的形式,令 $a_i=\dfrac{(-1)^i}{i!}, b_i=i!*f_i$ ,把数列A反转, $g_k=\sum_{i+j=k}a^T[i]*b[j]$ ,卷在一起再除以 $i!$ 就表示 $g_i$

这里需要注意,把 $A$ 反转后, $i->N-i$ ,则 $A_{j-i}=A^T_{N-(j-i)}=A^T_{N-j+i}$ ,所以原式变成了: $\sum_{j+k=N+i}A_j*B_k$

5.CF1251F

考虑把所有询问/2,枚举中间的红块是哪个,假设当前红块高度为x,比x小的 $a_i$ 有y个,用的白块数量(可以根据询问x值唯一确定)为 $z$

如果所有的 $a_i$ 都只有一个,那么答案是 $2^y*\dbinom{y}{z}$

如果所有的 $a_i$ 都大于一个,首先可以转化为只有两个,然后答案为: $\dbinom{y*2}{z}$

考虑记: $f_i=2^i*\dbinom{u}{i},g_i=\dbinom{2*v}{i}$ ,其中 $u$ 表示小于 $x$ 的且出现次数为 $1$ 的白板, $v$ 表示小于 $x$ 且出现次数不为 $1$ 的白板

把两个多项式卷在一起,再把所有红版加在一起,就可以得到每一个询问的答案了

6.CF755G

首先暴力 $DP$ 为设 $dp_{i\ j}$ 表示前i个数,分了j个集合的方案数,转移可以用 $dp_{i\ j} = dp_{i - 1\ j} + dp_{i - 1\ j - 1} + dp_{i - 2\ j - 1}$

这样转移的复杂度不能接受,考虑换一种转移方式:状态还是一样的,考虑转移

枚举一个分界点 $x$ ,分两种情况考虑: $1.$ 不跨过 $a,b$ , $2.$ 跨过 $a,b$ ,这样可以保证不重不漏

分开转移: $Case1:\ dp_{a+b\ j}=\sum dp_{a\ x} * dp_{b\ j-x}$ , $Case2:dp_{a+b\ j} = \sum dp_{a-1\ x - 1}*dp_{b-1\ j-x}$

然后不难发现这是一个多项式的形式,把 $dp$ 值看成多项式系数,我们只要知道了 $a$ , $b$ 的多项式,相乘就变成了 $a+b$ 的多项式

把 $2^x$ 的多项式预处理出来,用倍增跑一遍 $FFT$ 即可

7.万径人踪灭

一句话题意:求出所有位置与权值都关于某个位置对称,且不是连续的串的个数

答案等于:所有位置与权值都关于某个位置对称 - 回文串个数

后面的东西可以用 $Manachar$ 来求出,求出 $p_i$ 数组后,加起来就是答案

然后考虑前面的柿子:找到对称轴 $x$ ,往两边拓展,如果 $a[x-i]=a[x+i]$ 就让 $f[x]++$ ,最后的答案为 $\sum 2^{f[x]}-1$

考虑 $f[x]=\sum [a[x-i] == a[x+i]]$ ,发现这是一个卷积的形式,把 $a, b$ 分开考虑,把每个a设为1,把b设为0,然后跑 $FFT$ 即可

8.P4091 [HEOI2016/TJOI2016]求和

首先发现,如果 $j>i$ , $S(i,j)=0$ ,所以对答案无影响,于是 $j$ 的范围也可以扩充到N

第二类斯特林数带进去,用等比数列求和展开,于是我们最后可以得到: $f(n)=\sum_{j=0}^n2^j*j!*\sum_{k+l=j}\dfrac{(-1)^k}{k!}*\dfrac{l^{n+1}-1}{(l-1)*l!}$ ,卷积即可

P3702 序列计数

设 $dp[i][j]$ 为前i个数选择的数对p取模模数为j,然后类似上面 $T6$ 做法即可