2022.03.01 FFT与NNT
2022.03.01 FFT与NNT
https://www.luogu.com.cn/blog/wangrx/solution-p1919
https://www.luogu.com.cn/blog/attack/solution-p38032
P3803 【模板】多项式乘法（FFT）（NTT模板）
https://www.luogu.com.cn/problem/P3803
#include
using namespace std;
#define int long long
const int N=3e6+10;
const int mod=998244353;
const int G=3;
const int Gi=332748118;
int n,m,limit=1,len,rev[N],a[N],b[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
inline int powi(int x,int y){
int fin=1;
while(y){
if(y&1)fin=fin*x%mod;
x=x*x%mod;
y>>=1;
}
return fin;
}
inline void NTT(int *A,int flag){
for(int i=0;i>1]>>1)|((i&1)<<(len-1));
NTT(a,1);NTT(b,1);
for(int i=0;i P1919 【模板】A*B Problem 升级版（FFT 快速傅里叶变换（注意：可能结果的第一个系数也要进一……）（NTT模板1.1）
https://www.luogu.com.cn/problem/P1919
这里对于NTT模板进行了优化：
- 不用每次计算
powi(flag==1?3:inv3,(mod-1)/(mid<<1))了，直接搞了两个数组，一个叫powi3就是存3的次方的，一个叫powinv3就是存3的次方的逆元的 - 没了/斜眼笑
#include
using namespace std;
#define int long long
const int N=4e6+10;
const int mod=998244353;
int n,a[N],b[N],c[N],rev[N],lena,lenb;
int pow3[N],powinv3[N],inv3,inv,limit=1,len;
char s[N];
inline int powi(int x,int y){
int fin=1;
while(y){
if(y&1)fin=fin*x%mod;
x=x*x%mod;y>>=1;
}
return fin;
}
inline void NTT(int *A,int flag){
for(int i=0;i>1]>>1)|((i&1)<<(len-1));
for(int i=1;i<=limit;i<<=1)
pow3[i]=powi(3,(mod-1)/i),powinv3[i]=powi(inv3,(mod-1)/i);
NTT(a,1);NTT(b,1);
for(int i=0;i=10)c[i+1]+=c[i]/10,c[i]%=10;
n=lena+lenb+4;
while(c[n]==0)--n;
for(int i=n;i>=0;i--)cout< P2553 [AHOI2001]多项式乘法
https://www.luogu.com.cn/problem/P2553
这是道美丽的字符串，但是eleveni挂在NTT上
#include
using namespace std;
#define int long long
const int N=666;
const int mod=998244353;
int limit=1,a[N],b[N],rev[N],len,inv,inv3,powi3[N],powinv3[N];
struct node{
int x,y;
bool operator <(const node &b)const{
return y>=1;
}
return fin;
}
inline void NTT(int *A,int flag){
for(int i=0;i='0'&&t[i]<='9'){
x=x*10+t[i]-'0';i++;
}
++tot;
s[tot].x=x;
if(t[i]!=')'){
i+=2;
x=0;
while(t[i]>='0'&&t[i]<='9'){
x=x*10+t[i]-'0';i++;
}
s[tot].y=x;
}
if(t[i]=='+')i++;
}
}
if(!cheng){
cout<>1]>>1)|((i&1)<<(len-1));
//cout<<"Case 1 "<=0;i--)
if(i>0&&a[i]>0){
printf("%da^%d",a[i],i);
if(cheng!=i)printf("+");
}else if(i==0&&a[i])printf("%d",a[i]);
cout< P3338 [ZJOI2014]力（FTT模板1.0）
https://www.luogu.com.cn/problem/P3338
不知道为什么，重构一遍就过了……
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=4e5+10;
const double pi=acos(-1.0);
int n,limit=1,len,rev[N];
struct node{
double x,y;
node(double xi=0,double yi=0){
x=xi;y=yi;
}
node operator +(const node &b)const{
return {x+b.x,y+b.y};
}
node operator -(const node &b)const{
return {x-b.x,y-b.y};
}
node operator *(const node &b)const{
return {x*b.x-y*b.y,x*b.y+y*b.x};
}
}H[N],G[N],I[N];
inline void FFT(node *A,double flag){
for(int i=0;i>n;
for(int i=1;i<=n;i++){
cin>>H[i].x;
G[n-i+1].x=H[i].x;
I[i].x=(double)1/(double)i/(double)i;
}
while(limit<=(n<<1))limit<<=1,++len;
for(int i=0;i>1]>>1)|((i&1)<<(len-1));
FFT(H,1);FFT(G,1);FFT(I,1);
for(int i=0;i<=limit;i++)H[i]=H[i]*I[i],G[i]=G[i]*I[i];
FFT(H,-1);FFT(G,-1);
for(int i=0;i<=limit;i++)H[i].x/=limit,G[i].x/=limit;
for(int i=1;i<=n;i++)printf("%.4lf\n",H[i].x-G[n-i+1].x);
return 0;
}