2022.5.21 $\text{FFT/NTT(unfinished)}$
听了两节课了，懂了但没完全懂。
不过倒是听了一点复数和原根的知识
暂且放个代码吧......
\(\text{W! S! F! W!}\)
（有一些来不及整理的截图，见文件）
$\text{F F T}$ 模板
#include
#include
#include
#include
#define MAXN 4000010
int n,m;
struct complex{
double real,imag;
complex(){real=imag=0.0;}
complex(double x){real=x,imag=0.0;}
complex(double x,double y){real=x,imag=y;}
complex operator + (const complex &a)const{
return complex(real+a.real,imag+a.imag);
}
complex operator - (const complex &a)const{
return complex(real-a.real,imag-a.imag);
}
complex operator * (const complex &a)const{
return complex(real*a.real-imag*a.imag,imag*a.real+real*a.imag);
}
void operator /= (const double x){
real/=x,imag/=x;
}
}A[MAXN],B[MAXN],u[MAXN];
int lowbit(int x){
return x&-x;
}
int bit_reverse(int x,int size){
int res=0;
for(int i=x;i;i-=lowbit(i)){
res|=size/2/lowbit(i);
}
return res;
}
void fft(complex *A,int size,bool flag){
for(int i=0;i>1,addgap=size/step;
for(int i=0;i'9') w|=(ch=='-'),ch=getchar();
while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
int main(){
//freopen("input","r",stdin);
std::cin>>n>>m;n++,m++;
int size=1;
while(size $\text{f f t}$ 函数
#include
#include
typedef std::complex Comp; // STL complex
const Comp I(0, 1); // i
const int MAX_N = 1 << 20;
Comp tmp[MAX_N];
void DFT(Comp *f, int n, int rev) { // rev=1,DFT; rev=-1,IDFT
if (n == 1) return;
for (int i = 0; i < n; ++i) tmp[i] = f[i];
for (int i = 0; i < n; ++i) { // 偶数放左边，奇数放右边
if (i & 1)
f[n / 2 + i / 2] = tmp[i];
else
f[i / 2] = tmp[i];
}
Comp *g = f, *h = f + n / 2;
DFT(g, n / 2, rev), DFT(h, n / 2, rev); // 递归 DFT
Comp cur(1, 0), step(cos(2 * M_PI / n), sin(2 * M_PI * rev / n));
// Comp step=exp(I*(2*M_PI/n*rev)); // 两个 step 定义是等价的
for (int k = 0; k < n / 2; ++k) {
tmp[k] = g[k] + cur * h[k];
tmp[k + n / 2] = g[k] - cur * h[k];
cur *= step;
}
for (int i = 0; i < n; ++i) f[i] = tmp[i];
}
$\text{N T T}$
#include
#include
using namespace std;
typedef long long ll;
const int N=1e7+5,P=998244353,P1=3,P2=332748118; // P2是P1的逆元
int lena,lenb,n=1,lim,r[N];
ll a[N],b[N];
ll rpow(ll x,ll y){//要手打
ll res=1;
while(y){
if(y&1)res=(res*x)%P;
x=(x*x)%P;
y>>=1;
}
return res%P;
}
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
void NTT(ll *A,int tp){
for(int i=0;i>1]>>1)|((i&1)<<(lim-1));
NTT(a,1);
NTT(b,1);
for(int i=0;i<=n;i++)a[i]=(a[i]*b[i])%P;
NTT(a,0);
ll inv=rpow(n,P-2);
for(int i=0;i<=lena+lenb;i++)printf("%d ",(a[i]*inv)%P);
}