所以求逆不香吗
by NaCly_Fish @ 2020-02-25 15:57:44
所以求逆不香吗
by command_block @ 2020-02-25 16:09:05
@[huangzirui](/user/35891) 写丑了吧，len每次乘法都要求一遍，像这样：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N=1<<18;
const int Mod=998244353,g=3;
int A[MAX_N],B[MAX_N],C[MAX_N];
int F[MAX_N],G[MAX_N],n;
int n1,n2,rev[MAX_N];
int bin_pow(int a,int b)
{
int ret=1;
while(b>0)
{
if(b%2)ret=ret*a%Mod;
a=a*a%Mod;
b/=2;
}
return ret;
}
void NTT(int A[],int n,int flag)
{
for(int i=0;i<n;i++)if(rev[i]>i)swap(A[i],A[rev[i]]);
for(int i=1;i<n;i<<=1)
{
int w1=bin_pow(g,(Mod-1)/(i<<1));
if(flag==-1)w1=bin_pow(w1,Mod-2);
for(int j=0;j<n;j+=(i<<1))
{
int w2=1;
for(int k=0;k<i;k++)
{
int t1=A[j+k],t2=A[i+j+k]*w2%Mod;
A[j+k]=(t1+t2)%Mod;
A[i+j+k]=(t1-t2+Mod)%Mod;
w2=w2*w1%Mod;
}
}
}
int t=bin_pow(n,Mod-2);
if(flag==-1)for(int i=0;i<n;i++)A[i]=A[i]*t%Mod;
}
void multiple(int t1[],int n1,int t2[],int n2,int rec[])
{
int len=1,L=0;
while(len<=n1+n2)
{
len<<=1;
L++;
}
for(int i=1;i<len;i++)rev[i]=rev[i>>1]>>1|(i&1)<<(L-1);
for(int i=0;i<len;i++)A[i]=0;
for(int i=0;i<len;i++)B[i]=0;
for(int i=0;i<=n1;i++)A[i]=t1[i];
for(int i=0;i<=n2;i++)B[i]=t2[i];
NTT(A,len,1);
NTT(B,len,1);
for(int i=0;i<len;i++)C[i]=A[i]*B[i]%Mod;
NTT(C,len,-1);
for(int i=n1+1;i<=n2;i++)rec[i]=(rec[i]+C[i])%Mod;
}
void solve(int l,int r)
{
if(l>=r)return;
int mid=(l+r)/2;
solve(l,mid);
multiple(F+l,mid-l,G,r-l,F+l);
solve(mid+1,r);
}
signed main()
{
cin>>n;
for(int i=1;i<n;i++)cin>>G[i];
F[0]=1;
int len=1;
while(len<=n)len<<=1;
solve(0,len-1);
for(int i=0;i<n;i++)cout<<F[i]<<" \n"[i==n-1];
return 0;
}
```
by Smile_Cindy @ 2020-02-25 16:10:40
@[command_block](/user/58705) @[NaCly_Fish](/user/115864)
求逆是可以做但这是分治FFT板子题啊（
by Smile_Cindy @ 2020-02-25 16:11:15
@[Alpha](/user/87058) ?
len 我的确是每次FFT前都重新算的啊qaq
by huangzirui @ 2020-02-25 16:25:47
所以正解是不用递归？qaq
by huangzirui @ 2020-02-25 16:26:27
@[huangzirui](/user/35891)
我明白了，你这样不挂才怪
```cpp
for(int i=1;i<=n;i++)B[i]=a[i];
```
每次递归都for了一遍
by Smile_Cindy @ 2020-02-25 17:52:41
我之前都整了啥无知言论啊,该好好学学了 (
by command_block @ 2020-05-05 22:05:08