【Uoj34】多项式乘法(NTT,FFT)

时间:2023-01-10 10:55:51

【Uoj34】多项式乘法(NTT,FFT)

题面

uoj

题解

首先多项式乘法用\(FFT\)是一个很久很久以前就写过的东西

直接贴一下代码吧。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<complex>
using namespace std;
#define ll long long
#define RG register
#define MAX 300000
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
const double Pi=acos(-1);
complex<double> a[MAX],b[MAX];
int r[MAX],n,m,l;
void FFT(complex<double> *P,int opt)
{
for(int i=0;i<n;++i)if(i<r[i])swap(P[i],P[r[i]]);
for(int i=1;i<n;i<<=1)
{
complex<double> W(cos(Pi/i),opt*sin(Pi/i));
for(int p=i<<1,j=0;j<n;j+=p)
{
complex<double> w(1,0);
for(int k=0;k<i;w*=W,++k)
{
complex<double> X=P[j+k],Y=w*P[i+j+k];
P[j+k]=X+Y;P[i+j+k]=X-Y;
}
}
}
}
int main()
{
n=read();m=read();
for(int i=0;i<=n;++i)a[i]=read();
for(int i=0;i<=m;++i)b[i]=read();
m+=n;
for(n=1;n<=m;n<<=1)++l;
for(int i=0;i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
FFT(a,1);FFT(b,1);
for(int i=0;i<n;++i)a[i]*=b[i];
FFT(a,-1);
for(int i=0;i<=m;++i)printf("%d ",(int)(a[i].real()/n+0.5));
puts("");
return 0;
}

我们知道\(FFT\)中使用单位复根

满足两个引理

\[(W_{2n}^k)^2=W_{n}^{k}
\]

\[W_{n}^k=-W_{n}^{k+n/2}
\]

单位复根在算的过程中很容易出现精度的问题

现在要找到一个拥有相同性质的东西能够代替单位复根就好了

主要是第二个性质难找

因为\(W_n\)是\(n\)次单位复根

所以:\((W_n)^n=1,(W_n)^{n/2}=-1\)

其实,这个性质可以被原根满足:

假设\(p\)的原根是\(g\)

再膜\(p\)意义下:

\(g^{\varphi(p)}=1\to g^{\varphi(p)/2}=\sqrt {1}\)

因为原根不存在一个比\(\varphi(p)\)小的数使得\(g^k=1\)

所以\(g^{\varphi(p)/2}=-1\)

我们发现上面的性质也可以满足

所以,把\(n\)次单位复根可以替换成原根的\(\varphi(p)/(2^n)\)来做

这样就解决了小数精度的问题

当然也是用来解决卷积取膜的问题

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 3000000
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
const int pr=3;
const int MOD=998244353;
const int phi=MOD-1;
int n,m,r[MAX],l;
int a[MAX],b[MAX];
int fpow(int a,int b)
{
int s=1;
while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}
return s;
}
void NTT(int *P,int opt)
{
for(int i=0;i<n;++i)if(i<r[i])swap(P[i],P[r[i]]);
for(int i=1;i<n;i<<=1)
{
int W=fpow(pr,phi/(i<<1));
for(int p=i<<1,j=0;j<n;j+=p)
{
int w=1;
for(int k=0;k<i;++k,w=1ll*w*W%MOD)
{
int X=P[j+k],Y=1ll*w*P[i+j+k]%MOD;
P[j+k]=(X+Y)%MOD;P[i+j+k]=(X-Y+MOD)%MOD;
}
}
}
if(opt==-1)reverse(&P[1],&P[n]);
}
int main()
{
n=read();m=read();
for(int i=0;i<=n;++i)a[i]=read();
for(int i=0;i<=m;++i)b[i]=read();
m+=n;
for(n=1;n<=m;n<<=1)++l;
for(int i=0;i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
NTT(a,1);NTT(b,1);
for(int i=0;i<n;++i)a[i]=1ll*a[i]*b[i]%MOD;
NTT(a,-1);
int inv=fpow(n,MOD-2);
for(int i=0;i<n;++i)a[i]=1ll*a[i]*inv%MOD;
for(int i=0;i<=m;++i)printf("%d ",a[i]);puts("");
return 0;
}

【Uoj34】多项式乘法(NTT,FFT)的更多相关文章

  1. FFT&sol;NTT总结&plus;洛谷P3803 【模板】多项式乘法(FFT)(FFT&sol;NTT)

    前言 众所周知,这两个东西都是用来算多项式乘法的. 对于这种常人思维难以理解的东西,就少些理解,多背板子吧! 因此只总结一下思路和代码,什么概念和推式子就靠巨佬们吧 推荐自为风月马前卒巨佬的概念和定理 ...

  2. 洛谷P3803 【模板】多项式乘法(FFT)

    P3803 [模板]多项式乘法(FFT) 题目背景 这是一道FFT模板题 题目描述 给定一个n次多项式F(x),和一个m次多项式G(x). 请求出F(x)和G(x)的卷积. 输入输出格式 输入格式: ...

  3. 洛谷 P3803 【模板】多项式乘法(FFT)

    题目链接:P3803 [模板]多项式乘法(FFT) 题意 给定一个 \(n\) 次多项式 \(F(x)\) 和一个 \(m\) 次多项式 \(G(x)\),求 \(F(x)\) 和 \(G(x)\) ...

  4. 【luogu P3803】【模板】多项式乘法(FFT)

    [模板]多项式乘法(FFT) 题目链接:luogu P3803 题目大意 给你两个多项式,要你求这两个多项式乘起来得到的多项式.(卷积) 思路 系数表示法 就是我们一般来表示一个多项式的方法: \(A ...

  5. UOJ34 多项式乘法(NTT)

    本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/ ...

  6. 多项式乘法,FFT与NTT

    多项式: 多项式?不会 多项式加法: 同类项系数相加: 多项式乘法: A*B=C $A=a_0x^0+a_1x^1+a_2x^2+...+a_ix^i+...+a_{n-1}x^{n-1}$ $B=b ...

  7. 多项式乘法(FFT)模板 &amp&semi;&amp&semi; 快速数论变换(NTT)

    具体步骤: 1.补0:在两个多项式最前面补0,得到两个 $2n$ 次多项式,设系数向量分别为 $v_1$ 和 $v_2$. 2.求值:用FFT计算 $f_1 = DFT(v_1)$ 和 $f_2=DF ...

  8. 洛谷P3803 【模板】多项式乘法 &lbrack;NTT&rsqb;

    题目传送门 多项式乘法 题目描述 给定一个n次多项式F(x),和一个m次多项式G(x). 请求出F(x)和G(x)的卷积. 输入输出格式 输入格式: 第一行2个正整数n,m. 接下来一行n+1个数字, ...

  9. 【总结】对FFT的理解 &sol; 【洛谷 P3803】 【模板】多项式乘法(FFT)

    题目链接 \(\Huge\text{无图,慎入}\) \(FFT\)即快速傅里叶变换,用于加速多项式乘法. 如果暴力做卷积的话就是一个多项式的每个单项式去乘另一个多项式然后加起来,时间复杂度为\(O( ...

  10. UVALive - 6886 Golf Bot 多项式乘法(FFT)

    题目链接: http://acm.hust.edu.cn/vjudge/problem/129724 Golf Bot Time Limit: 15000MS 题意 给你n个数,m个查询,对于每个查询 ...

随机推荐

  1. flex 添加svn插件

    http://blog.csdn.net/gangan1345/article/details/7926848

  2. list 集合

    1.Model public class ROLE_FUNCTION { //角色集合 public List< ROLE> ROLES { get; set; } //角色权限集合 pu ...

  3. apache安装错误error&colon; APR not found解决办法

    linux安装时安装种类不同,一些组件包可能不会被安装,导致linux下安装软件的时候缺这个缺那个,今天为大家介绍linux安装apache时报apr找不到的解决办法 方法/步骤   下载依赖包 wg ...

  4. 洛谷1377 M国王 (SCOI2005互不侵犯King)

    洛谷1377 M国王 (SCOI2005互不侵犯King) 本题地址:http://www.luogu.org/problem/show?pid=1377 题目描述 天天都是n皇后,多么无聊啊.我们来 ...

  5. Android ExpandableListActivity的简单介绍及小例子

    Android中常常要用到ListView,但也经常要用到ExpandableListView,ListView是显示列表,而ExpandableListView显示的是分类的列表: 下面用一个例子来 ...

  6. Lintcode393 Best Time to Buy and Sell Stock IV solution 题解

    [题目描述] Say you have an array for which the i th element is the price of a given stock on day i. Desi ...

  7. python历史与基本类型

    前言 我自学的方式主要是看文档,看视频,第一次做写博客这么神圣的事情,内心是忐忑的,写的东西比较杂,路过的小伙伴不要嘲笑我,主要是记录一日所学,顺便锻炼一下语言组织能力吧,anyway,这些都不重要, ...

  8. Django model update的各种用法介绍

    Django开发过程中对表(model)的增删改查是最常用的功能之一,本文介绍笔者在使用model update过程中遇到的那些事 model update常规用法 假如我们的表结构是这样的 clas ...

  9. 搭建GitLab&plus;Jenkins

    1. Jenkins and GitLab Jenkins是一个自动化服务器,可以运行各种自动化构建.测试或部署任务. GitLab是一个代码仓库,用来管理代码. 两者结合起来,就可以实现开发者提交代 ...

  10. 在懂得BREW接口的原理之后&comma; 那么该知道BREW接口是如何声明和实现了

    参考:http://blog.csdn.net/peteryxk/article/details/1584514 首先介绍几个用到的宏定义: l         #define VTBL(iname) ...