多项式/卷积相关(板子

又将是一篇除了板子啥都没有的博...

虽然可能在板子前胡一堆东西,但其实都是废话。。

卷积与DFT

形如这样的式子被成为卷积:

[c_k=sum_{icirc j=k}a_ib_j ]

其中 (circ) 为任意一种运算。当它为 (+) 时该卷积即为多项式卷积。不难发现 (left{cright}) 即为系数分别为 (left{aright})(left{bright}) 的多项式相乘后得到多项式的系数。

直接计算卷积是 (O(n^2)) 的。考虑对三个序列进行变换,使变换后得到的 (hat a)(hat b)(hat c) 满足如下式子

[hat{c_i}=hat{a_i}hat{b_i} ]

也就是将卷积转换为了对位相乘,这样就可以 (O(n)) 完成卷积。最后再通过某种方式将变换映射回去即可。

一种方便的方法是离散傅里叶变换DFT。它将 (n-1) 次多项式 (f) 的系数向量 (vec a=(a_0,a_1,ldots,a_{n-2},a_{n-1})) 转化为点值向量 (vec y=(f(omega_n^0),f(omega_n^1),ldots,f(omega_n^{n-2}),f(omega_n^{n-1}))) 。其中 (omega_n)(n) 次单位根,即复数域内 (x^n=1) 的解。一般选用幅角最小的那个,即 (cos(frac{2pi}{n})+sin(frac{2pi}{n})i)

选择单位根作为点值的横坐标是因为它很多优秀的性质。这里不表不会。可以参考周指导の指导。(其实这篇博大部分东西都是这里学的

FFT

利用复数域内单位根的性质加速离散傅里叶变换过程的算法。

具体性质不会。可以跟周指导学习一波。

因为不大能理解,一开始背板在FFT部分属实有些煎熬。这里加一点没有逻辑的注释。

void fft(complex *a,int n){     for(int i=0;i<n;i++)         if(r[i]>i) swap(a[i],a[r[i]]); //提出要迭代的序列,先处理r[i]     for(int t=n>>1,d=1;d<n;t>>=1,d<<=1) //d为迭代区间长度的一半,t为计算单位根次数的系数         for(int i=0;i<n;i+=(d<<1)) //i为当前迭代区间的左端点             for(int j=0;j<d;j++){ //j为当前处理的位置                 complex tmp=w[t*j]*a[i+j+d];                 a[i+j+d]=a[i+j]-tmp;                 a[i+j]=a[i+j]+tmp;             } } 

不能帮助理解,但能帮助记忆

洛谷P3803[模板]多项式乘法
#include<bits/stdc++.h> using namespace std;  namespace IO{     typedef long long LL;     typedef double DB;     int read(){         int x=0,f=0; char ch=getchar();         while(ch>'9'||ch<'0'){ f|=(ch=='-'); ch=getchar(); }         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }         return f?-x:x;     } char output[50];     void write(int x,char sp){         int len=0;         if(x<0) putchar('-'), x=-x;         do{ output[len++]=x%10+'0'; x/=10; }while(x);         for(int i=len-1;~i;i--) putchar(output[i]); putchar(sp);     }     void ckmax(int& x,int y){ x=x>y?x:y; }     void ckmin(int& x,int y){ x=x<y?x:y; } } using namespace IO;  const int NN=1<<22; int dega,degb;  namespace Poly_Calculation{     const DB PI=acos(-1.0);     struct complex{         DB r,i;         complex(){ r=i=0; }         complex(DB x,DB y){ r=x; i=y; }         complex operator+(const complex& t)const{ return complex(r+t.r,i+t.i); }         complex operator-(const complex& t)const{ return complex(r-t.r,i-t.i); }         complex operator*(const complex& t)const{ return complex(r*t.r-i*t.i,r*t.i+i*t.r); }     }a[NN],b[NN],w[NN];     int l,len,r[NN];     void prework(){         for(len=1;len<=dega+degb;len<<=1) ++l;         for(int i=0;i<len;i++){             r[i]=(r[i>>1]>>1)|((i&1)<<l-1);             w[i]=complex(cos(2.0*i*PI/len),sin(2.0*i*PI/len));         }     }     void fft(complex *a,int n){         for(int i=0;i<n;i++)             if(r[i]>i) swap(a[i],a[r[i]]);         for(int t=n>>1,d=1;d<n;t>>=1,d<<=1)             for(int i=0;i<n;i+=(d<<1))                 for(int j=0;j<d;j++){                     complex tmp=w[t*j]*a[i+j+d];                     a[i+j+d]=a[i+j]-tmp;                     a[i+j]=a[i+j]+tmp;                 }     }     void poly_mul(complex *a,complex *b){         fft(a,len); fft(b,len);         for(int i=0;i<len;i++)             a[i]=a[i]*b[i], w[i].i=-w[i].i;         fft(a,len);         for(int i=0;i<len;i++) a[i].r=a[i].r/len;     } } using namespace Poly_Calculation;  signed main(){     dega=read()+1; degb=read()+1;     for(int i=0;i<dega;i++) a[i].r=read();     for(int i=0;i<degb;i++) b[i].r=read();     prework(); poly_mul(a,b);     --dega; --degb;     for(int i=0;i<=dega+degb;i++)         write(int(a[i].r+0.5),' ');     return puts(""),0; } 

NTT

虽然FFT已经可以完成快速多项式卷积的工作,但它也存在一些弊端。如精度问题,以及涉及取模时无法方便运算等。

这时就需要使用NTT。大体来讲,NTT与FFT的原理是完全一致的,只不过使用模意义下的原根(的整数次幂)代替了复数域内的单位根,避免了浮点数计算。

经过一些推导,令模数意义下原根为 (g) ,那么原来的 (w_n) 就可以替换为 (g^{frac{mod-1}{n}})

因为多项式长度都取 (2) 的整数次幂,所以要求 (g) 的指数为整数,对模数有一些要求。

两个常见的模数: (998244353)(1004535809) ,原根都为 (3)

板子方面几乎跟FFT一模一样啊。。

洛谷P3803[模板]多项式乘法
#include<bits/stdc++.h> using namespace std;  namespace IO{     typedef long long LL;     typedef double DB;     LL read(){         LL x=0,f=0; char ch=getchar();         while(ch>'9'||ch<'0'){ f|=(ch=='-'); ch=getchar(); }         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }         return f?-x:x;     } char output[50];     void write(LL x,char sp){         int len=0;         if(x<0) putchar('-'), x=-x;         do{ output[len++]=x%10+'0'; x/=10; }while(x);         for(int i=len-1;~i;i--) putchar(output[i]); putchar(sp);     }     void ckmax(int& x,int y){ x=x>y?x:y; }     void ckmin(int& x,int y){ x=x<y?x:y; } } using namespace IO;  const int NN=1<<22,mod=998244353; int dega,degb; LL qpow(LL a,LL b=mod-2,LL res=1){     for(;b;b>>=1,a=a*a%mod)         if(b&1) res=res*a%mod;     return res; }  namespace Poly_Calculation{     LL l,len,inv,g[NN],r[NN],a[NN],b[NN];     void prework(){         for(len=1;len<=dega+degb;len<<=1) ++l;         for(int i=0;i<len;i++)             r[i]=(r[i>>1]>>1)|((i&1)<<l-1);         g[0]=1; g[1]=qpow(3,(mod-1)/len);         for(int i=2;i<len;i++) g[i]=g[i-1]*g[1]%mod;     }     void ntt(LL *a,int n){         for(int i=0;i<n;i++)             if(r[i]>i) swap(a[r[i]],a[i]);         for(int t=n>>1,d=1;d<n;d<<=1,t>>=1)             for(int i=0;i<n;i+=(d<<1))                 for(int j=0;j<d;j++){                     LL tmp=g[t*j]*a[i+j+d]%mod;                     a[i+j+d]=(a[i+j]-tmp+mod)%mod;                     a[i+j]=(a[i+j]+tmp)%mod;                 }     }     void poly_mul(LL *a,LL *b){         ntt(a,len); ntt(b,len);         for(int i=0;i<len;i++)             a[i]=a[i]*b[i]%mod, g[i]=qpow(g[i]);         ntt(a,len);         inv=qpow(len);         for(int i=0;i<len;i++) a[i]=a[i]*inv%mod;     } } using namespace Poly_Calculation;  signed main(){     dega=read()+1; degb=read()+1;     for(int i=0;i<dega;i++) a[i]=read();     for(int i=0;i<degb;i++) b[i]=read();     prework(); poly_mul(a,b);     --dega; --degb;     for(int i=0;i<=dega+degb;i++)         write(a[i],' ');     return puts(""),0; } 

推荐这些技术文章:

上海月赛《打印漏斗》

#include <iostream>using namespace std;int main() { int n; cin >> n; for (int i = 1; i <= n - 1 ; i++) { for (int j = 1; j <= i - 1; j++) { cout << ' ...

多项式工业基础与全家桶

多项式工业基础与全家桶
开坑待填,放个常数巨大的板子先
#define Maxn 200005
#define mod 998244353
inline int ksm(int x,int y=mod-2)
{
int ret=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
return ret;
}
...

C++命名空间(namespace)提出的原因及解决的问题

目录命名空间只能全局范围内定义命名空间可嵌套命名空间命名空间可以随时把新的成员加入已有的命名空间中声明和实现可分离无名(匿名)命名空间,相当于给这个标识符加上了static【只能在本文件内访问】命名空间别名实际案例

返回 我的技术栈(Technology Stack)

在c++中,名称(name)可以是符号常量、变量、函数、结构、枚举、类和对象等等。
工程越大,名称互相冲突性的可能性越大。...

LuoguP5488 差分与前缀和 (多项式 组合数学 生成函数)

前置知识:
二项式定理

杨辉三角 第n行第m个数为C n-1, m-1

把前缀和 化成卷积的形式:

这时一个斜着的杨辉三角

现在我们知道了两种情况下b[i]的系数,因为是组合数,k超级大,所以递推出每一个bi.
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(f...

ZR 19CSP-S赛前冲刺day5 密码小明

T1
考虑树是0花费。
T2
二分容斥。
容斥是\(2^k\)
考虑到60以上的贡献系数都是1。
dp出容斥系数。
容斥就是\(log\)了
(高精开根是真的神仙,get到了)
T3
=三个题。
sub1 贪心选取。
sub2 01trie
sub3 FMT
FWT只学了\(or and\),没学\(xor\)。
以后可能会背板子了
#include <bits/stdc++.h>
...

读入及其优化:快读 & 快读不定个(多个)变量的方法 (可变模板参数快读)

众所周知 , c++常见的读入:
$\bullet $ 万能的 cin 大法,但却因流输入与 scanf 同步,在大数据中奇慢无比,只需关闭流同步,就能快的飞起。
划重点:前提是不能再使用 cstdio里的任何东西!包括但不限于scanf getchar
也就是加上一句。

ios::sync_with_stdio(false);

$\bullet$ 很吊但是很累的 scanf ,这里不作叙...

有条件的不重复排列问题

xmuoj
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 4;
ll f[N][2], n, k;
const ll mod = 1e9 + 7;

int main(){
cin >> n >> k;
f[1][0]...

【luogu P4721】【模板】分治 FFT(NTT)(多项式求逆 / cdq分治)

【模板】分治 FFT
题目链接:luogu P4721
题目大意
给你多项式 \(G\) 满足 \(G_0=0\)。
然后要你求多项式 \(F\) 的前 \(n\) 项满足:\(F_{i}=\sum\limits_{j=1}^iF_{i-j}G_j\)。
思路
cdq分治
你会发现对于一个你要求的范围 \([l,r]\),你如果求出了 \([l,mid]\),你就可以拿他来求它这个部分对 \([...

快速沃尔什变换小记

概述
\(FWT\)是用来处理集合卷积的问题。也就是求解\(f(n)\sum\limits_{i|j=n}f(i)f(j)\)类型的问题。其中或运算可以改为\(\otimes,\&\)。
寻找点值
因为总是看不下去那么长的推导,所以每次都是看到一半。然后就在加上自己的一点理解,简单推导一下吧(背过结论就行)
以或运算为例。为什么说是集合卷积呢。因为或运算等价于求集合并。也就是求\(f(n...

作业,复数的+-*/

 
 
 
 
 
 

#include<iostream>
#include<complex>
using namespace std;

class Complex
{
public:
Complex(){ r=0;i=0;}
void init(double real,double ima...

文章标题:多项式/卷积相关(板子
文章链接:https://www.dianjilingqu.com/2244.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>