登录
← 返回首页 | 代码片段 › 7 数论与数学 › 7.4 多项式与FFT › 多项式与FFT / 搜索
JSON MD

7.4 多项式与FFT

多项式乘法-快速傅里叶变换 FFT
85 行
CPP JSON
【快速傅里叶变换(FFT)——多项式乘法】 ▪ Complex — 复数结构体,支持 +、-、* 运算符重载(复数运算) ▪ getSize(n) — 计算 ≥n 的最小 2 的幂作为变换长度 ▪ change(a, n) — 位逆序重排(bit-reversal permutation),将系数数组重排为蝴蝶变换所需顺序 ▪ fft(a, n, opt) — 快速傅里叶变换核心:opt=1 正变换,opt=-1 逆变换;Cooley–Tukey 迭代算法,每层蝴蝶变换 O(N),共 log N 层 两个 n 次多项式乘法从 O(N²) 优化到 O(N log N)。适用于大整数乘法、生成函数卷积、信号处理。
C++ 85 行 CPP
struct Polynoial{
    struct Complex{
        double x,y;
        Complex(double _x = 0.0,double _y = 0.0){
            x = _x;
            y = _y;
        }
        Complex operator-(const Complex &rhs) const{
            return Complex(x-rhs.x,y-rhs.y);
        }
        Complex operator+(const Complex &rhs) const{
            return Complex(x+rhs.x,y+rhs.y);
        }
        Complex operator*(const Complex &rhs) const{
            return Complex(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);
        }
    };
    
    int getSize(int n) {
        int size = 1;
        while (size < n) size <<= 1;
        return size;
    }
    
    void change(vector<Complex>&a,int n){
        for(int i = 1,j = n/2;i < n-1;i++){
            if(i < j){
                swap(a[i],a[j]);
            }
            int k = n/2;
            while(j >= k){
                j -= k;
                k /= 2;
            }
            if(j < k)j += k;
        }
    }
    
    void fft(vector<Complex>&a,int n,int opt){
        change(a,n);
        for(int h = 2;h <= n;h*=2){
            Complex wn(cos(2*PI/h),sin(opt*2*PI/h));  // 修正:PI/h 而不是 PI/n
            for(int j = 0;j < n;j+=h){
                Complex w(1,0);
                for(int k = j;k < j+h/2;k++){
                    Complex u = a[k];
                    Complex t = w*a[k+h/2];
                    a[k]=u+t;
                    a[k+h/2]=u-t;
                    w=w*wn;
                }
            }
        }
        if(opt == -1){
            for(int i = 0;i < n;i++){
                a[i].x /= n;
            }
        }
    }

    vector<int> multiply(vector<int>& a, vector<int>& b) {
        int size = getSize(a.size() + b.size() - 1);
        
        vector<Complex> fa(size), fb(size);
        for(int i = 0; i < (int)a.size(); i++) fa[i] = Complex(a[i], 0);
        for(int i = 0; i < (int)b.size(); i++) fb[i] = Complex(b[i], 0);
        for(int i = a.size(); i < size; i++) fa[i] = Complex(0, 0);
        for(int i = b.size(); i < size; i++) fb[i] = Complex(0, 0);
        
        fft(fa, size, 1);
        fft(fb, size, 1);
        
        for(int i = 0; i < size; i++) {
            fa[i] = fa[i] * fb[i];
        }
        
        fft(fa, size, -1);
        
        vector<int> res(size);
        for(int i = 0; i < size; i++) {
            res[i] = (int)(fa[i].x + 0.5);
        }
        return res;
    }
};
Perpetual Subtraction 生成函数 移位
65 行
CPP JSON
【Perpetual Subtraction(生成函数 移位)】 多项式算法模板。 核心函数: template<typename T>inline void in(T &x) — 核心算法函数 int mi(Re x,LL k) — 核心算法函数 int Inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 关键配置: N=262144+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin);;for(Re i=0;i<=n;++i)printf("%d ",g0[i]);puts("");;for(Re i=0;i<=n;++i)printf("%d ",gm[i]);puts(""); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 64 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,invn,invG,f[N],g[N],g0[N],gm[N],f0[N],fm[N],tr[N],jc[N],inv[N],invjc[N];LL m;
template<typename T>inline void in(T &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,LL k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int Inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[len+i]%P;
				f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
	}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);invn=Inv(n),invG=Inv(G);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m);
    for(Re i=0;i<=n;++i)in(f0[i]);
    invjc[1]=invjc[0]=inv[1]=jc[1]=jc[0]=1;
    for(Re i=2;i<=n+1;++i)inv[i]=(LL)inv[P%i]*(P-P/i)%P,jc[i]=(LL)jc[i-1]*i%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P;
    
	for(Re i=0;i<=n;++i)f[i]=(LL)jc[n-i]*f0[n-i]%P,g[i]=invjc[i];
    times(f,n,g,n);
	for(Re i=0;i<=n;++i)g0[i]=(LL)f[n-i]*invjc[i]%P;
	
//	for(Re i=0;i<=n;++i)printf("%d ",g0[i]);puts("");
	for(Re i=0;i<=n;++i)gm[i]=(LL)g0[i]*mi(inv[i+1],m)%P;
//	for(Re i=0;i<=n;++i)printf("%d ",gm[i]);puts("");

	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(Re i=0;i<=n;++i)f[i]=(LL)jc[n-i]*gm[n-i]%P,g[i]=(LL)invjc[i]*((i&1)?P-1:1)%P;
	times(f,n,g,n);
	for(Re i=0;i<=n;++i)fm[i]=(LL)f[n-i]*invjc[i]%P;
	
	for(Re i=0;i<=n;++i)printf("%d ",fm[i]);
}
A×B Problem FFT
58 行
CPP JSON
【A×B Problem(FFT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 void FFT(CP *f,Re n,Re op) — 快速傅里叶变换 核心结构体:CP 关键配置: N=2097152+5 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+5;
const LD Pi=acos(-1);
int n,m,tr[N],Ans[N];char s1[N>>1],s2[N>>1];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct CP{
	LD x,y;
	CP(LD X=0,LD Y=0){x=X,y=Y;}
	inline CP operator+(const CP &O)const{return CP(x+O.x,y+O.y);}
	inline CP operator-(const CP &O)const{return CP(x-O.x,y-O.y);}
	inline CP operator*(const CP &O)const{return CP(x*O.x-y*O.y,x*O.y+y*O.x);}
	inline CP operator*=(const CP &O){return *this=*this*O;}
}f[N],g[N];
inline void FFT(CP *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1;
		CP w1(cos(2*Pi/p),sin(2*Pi/p));
		if(op)w1.y*=-1;
		for(Re st=0;st<n;st+=p){
			CP base(1,0);
			for(Re i=st;i<=st+len-1;++i){
				CP tmp=f[len+i]*base;
				f[len+i]=f[i]-tmp,f[i]=f[i]+tmp,base*=w1;
			}
		}
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%s%s",s1,s2),n=strlen(s1),m=strlen(s2);
	for(Re i=0;i<n;++i)f[i].x=s1[n-i-1]-'0';
	for(Re i=0;i<m;++i)g[i].x=s2[m-i-1]-'0';
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	FFT(f,n,0),FFT(g,n,0);
	for(Re i=0;i<n;++i)f[i]*=g[i];
	FFT(f,n,1);
	for(Re i=0;i<=m;++i){
		Ans[i]+=(int)(f[i].x/n+0.5);
		if(Ans[i]>9)Ans[i+1]+=Ans[i]/10,Ans[i]%=10,m+=(i==m);
	}
	while(!Ans[m]&&m>=1)--m;
	for(Re i=m;i>=0;--i)printf("%d",Ans[i]);
}
分治NTT 循环卷积优化
65 行
CPP JSON
【分治NTT(循环卷积优化)】 数论变换(NTT)模板,在模意义下计算多项式卷积,避免浮点误差。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void CDQ(Re L,Re R) — 核心算法函数 关键配置: N=131072+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 64 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=131072+3,P=998244353,G=3;
int n,m,invn,invG,f[N],g[N],A[N],tr[N],ans[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[i+len]%P;
				f[i+len]=(f[i]-tmp+P)%P;
				f[i]=(f[i]+tmp)%P;
				base=(LL)base*w1%P;
			}
	}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(n=1;n<=m;n<<=1);
	for(Re i=m+1;i<=n;++i)f[i]=g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
inline void CDQ(Re L,Re R){
	if(L==R)return;
	Re mid=L+R>>1;CDQ(L,mid);
	for(Re i=L;i<=R;++i)g[i-L]=A[i-L];
	for(Re i=L;i<=mid;++i)f[i-L]=ans[i];
	for(Re i=mid+1;i<=R;++i)f[i-L]=0;
	times(f,mid-L,g,R-L);
	for(Re i=mid+1;i<=R;++i)(ans[i]+=f[i-L])%=P;
	CDQ(mid+1,R);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),invG=inv(G);
	for(Re i=1;i<n;++i)in(A[i]);
	ans[0]=1,CDQ(0,n-1);
	for(Re i=0;i<n;++i)printf("%d ",ans[i]);
}
多项式 乘法 FFT
58 行
CPP JSON
【多项式 乘法(FFT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 void FFT(CP *f,Re n,Re op) — 快速傅里叶变换 void times(CP *f,Re n,CP *g,Re m) — 核心算法函数 核心结构体:CP 关键配置: N=2097152+3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 57 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+3;
const LD Pi=acos(-1);
int n,m,tr[N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct CP{
	LD x,y;CP(LD X=0,LD Y=0){x=X,y=Y;}
	inline CP operator+(const CP &O)const{return CP(x+O.x,y+O.y);}
	inline CP operator-(const CP &O)const{return CP(x-O.x,y-O.y);}
	inline CP operator*(const CP &O)const{return CP(x*O.x-y*O.y,x*O.y+y*O.x);}//(ac-bd,bc+ad)
	inline CP operator/(const CP &O)const{
		LD tmp=O.x*O.x+O.y*O.y;//tmp=c^2+d^2
		return CP((x*O.x+y*O.y)/tmp,(y*O.x-x*O.y)/tmp);//( (ac+bd)/tmp,(bc-ad)/tmp )
	}
	inline CP operator*=(const CP &O){return *this=*this*O;}
}f[N],g[N];
inline void FFT(CP *f,Re n,Re op){//op=0:DFT, op=1:IDFT
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1;CP w1(cos(2*Pi/p),sin(2*Pi/p));
		if(op)w1.y*=-1;
		for(Re st=0;st<n;st+=p){
			CP base(1,0);
			for(Re i=st;i<=st+len-1;++i){
				CP tmp=base*f[len+i];
				f[len+i]=f[i]-tmp,f[i]=f[i]+tmp,base*=w1;
			}
		}
	}
}
inline void times(CP *f,Re n,CP *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	FFT(f,n,0),FFT(g,n,0);
	for(Re i=0;i<n;++i)f[i]*=g[i];
	FFT(f,n,1);
	for(Re i=0;i<=m;++i)f[i].x/=n;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=0;i<=n;++i)scanf("%lf",&f[i].x);
	for(Re i=0;i<=m;++i)scanf("%lf",&g[i].x);
	times(f,n,g,m);
	for(Re i=0;i<=n+m;++i)printf("%d ",(int)(f[i].x+0.5));
}
多项式 乘法 NTT
51 行
CPP JSON
【多项式 乘法(NTT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 关键配置: N=2097152+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 50 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+3,P=998244353,G=3;
int n,m,invn,invG,f[N],g[N],tr[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[len+i]%P;
				f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
	}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);invn=inv(n),invG=inv(G);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=0;i<=n;++i)in(f[i]);
	for(Re i=0;i<=m;++i)in(g[i]);
	times(f,n,g,m);
	for(Re i=0;i<=n+m;++i)printf("%d ",f[i]);
}
多项式 位运算卷积 FWT
52 行
CPP JSON
【多项式 位运算卷积(FWT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int inv(Re x) — 求模逆元 void FWT(Re *f,Re n,Re op) — 核心算法函数 void sakura(Re *A,Re *B,Re n,Re id_) — 后缀数组 关键配置: N=131072+3,P=998244353 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 51 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=131072+3,P=998244353;
int n,m,inv2,A[N],B[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int inv(Re x){
	Re s=1,k=P-2;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
int id,f[N],g[N];
inline void FWT(Re *f,Re n,Re op){
	for(Re p=2;p<=n;p<<=1)
		for(Re st=1,len=p>>1;st<n;st+=p)
			for(Re j=st;j<=st+len-1;++j)
				if(id==1)(f[j+len]+=(op?P-f[j]:f[j]))%=P;
				else if(id==2)(f[j]+=(op?P-f[j+len]:f[j+len]))%=P;
				else{
					Re g0=f[j],g1=f[j+len];
					f[j]=(g0+g1)%P,f[j+len]=(g0-g1+P)%P;
					if(op)f[j]=(LL)f[j]*inv2%P,f[j+len]=(LL)f[j+len]*inv2%P;
				}
}
inline void sakura(Re *A,Re *B,Re n,Re id_){
	for(Re i=1;i<=n;++i)f[i]=A[i],g[i]=B[i];id=id_;
	FWT(f,n,0),FWT(g,n,0);
	for(Re i=1;i<=n;++i)f[i]=(LL)f[i]*g[i]%P;
	FWT(f,n,1);
	for(Re i=1;i<=n;++i)printf("%d ",f[i]);puts("");
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),n=(1<<n),inv2=inv(2);
	for(Re i=1;i<=n;++i)in(A[i]);
	for(Re i=1;i<=n;++i)in(B[i]);
	sakura(A,B,n,1),sakura(A,B,n,2),sakura(A,B,n,3);
}
多项式 快速幂 nlog^2n 暴力
67 行
CPP JSON
【多项式 快速幂(nlog^2n 暴力)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int in_(无参数) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void polymi(Re *x,Re n,Re k,Re *s) — 核心算法函数 关键配置: N=262144+3,P=998244353,G=3,phi=P-1 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 66 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int 
using namespace std;
const int N=262144+3,P=998244353,G=3,phi=P-1;
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
inline int in_(){
	int f=0;LL x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+(ch^48),x%=P,ch=getchar();
	return x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
	for(Re i=1;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)f[i+len]*base%P;
				f[i+len]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m){
	Re n_=n,m_=m;
	for(m+=n,n=1;n<=m;n<<=1);invG=inv(G);
	for(Re i=n_+1;i<n;++i)f[i]=0;
	for(Re i=m_+1;i<n;++i)g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);Re invn=inv(n);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int c[N];
inline void polymi(Re *x,Re n,Re k,Re *s){
	k%=P,s[0]=1;
	for(Re i=1;i<=n;++i)s[i]=0;
	while(k){
		if(k&1){for(Re i=0;i<=n;++i)c[i]=x[i];times(s,n,c,n);}
		for(Re i=0;i<=n;++i)c[i]=x[i];times(x,n,c,n),k>>=1;
	}
}
int n,K,f[N],g[N];
int main(){
//	freopen("123.txt","r",stdin);
	in(n),--n,K=in_();
	for(Re i=0;i<=n;++i)in(f[i]);
	polymi(f,n,K,g);
	for(Re i=0;i<=n;++i)printf("%d ",g[i]);
}
多项式 求逆 nlogn 优化倍增 NTT
59 行
CPP JSON
【多项式 求逆(nlogn 优化倍增 NTT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m,Re op=0) — 核心算法函数 void polyinv(Re *a,Re n,Re *b) — 求模逆元 关键配置: N=262144+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 58 行 CPP
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,A[N],B[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m,Re op=0){
	Re n_=n,m_=m;
	for(m+=n,n=1;n<=m;n<<=1);invG=inv(G);
	for(Re i=n_+1;i<n;++i)f[i]=0;
	for(Re i=m_+1;i<n;++i)g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P*(op?g[i]:1)%P;
	NTT(f,n,1);Re invn=inv(n);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int f[N],g[N];
inline void polyinv(Re *a,Re n,Re *b){
	if(n==0){b[0]=inv(a[0]);return;}
	polyinv(a,n>>1,b);
	for(Re i=0;i<=n;++i)f[i]=a[i],g[i]=b[i];
	times(f,n,g,n,1);
	for(Re i=0;i<=n;++i)b[i]=(2*b[i]%P-f[i]+P)%P;
}
int main(){
//    freopen("123.txt","r",stdin);
	in(n),--n;
	for(Re i=0;i<=n;++i)in(A[i]),A[i]%=P;
	polyinv(A,n,B);
	for(Re i=0;i<=n;++i)printf("%d ",B[i]);
}
多项式 求逆 nlog^2n 暴力分治 FFT
66 行
CPP JSON
【多项式 求逆(nlog^2n 暴力分治 FFT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void CDQ(Re L,Re R) — 核心算法函数 void polyinv(Re *a,Re n,Re *b) — 求模逆元 关键配置: N=262144+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 65 行 CPP
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,A[N],B[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(n=1;n<=m;n<<=1);invG=inv(G);
	for(Re i=m+1;i<n;++i)f[i]=g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);Re invn=inv(n);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int f[N],g[N],c[N],ans[N];
inline void CDQ(Re L,Re R){
	if(L==R)return;
	Re mid=L+R>>1;CDQ(L,mid);
	for(Re i=L;i<=R;++i)g[i-L]=c[i-L];
	for(Re i=L;i<=mid;++i)f[i-L]=ans[i];
	for(Re i=mid+1;i<=R;++i)f[i-L]=0;
	times(f,mid-L,g,R-L);
	for(Re i=mid+1;i<=R;++i)(ans[i]+=f[i-L])%=P;
	CDQ(mid+1,R);
}
inline void polyinv(Re *a,Re n,Re *b){
	Re tmp=inv(a[0]);c[0]=0;
	for(Re i=1;i<=n;++i)c[i]=(LL)(P-a[i])*tmp%P;
	ans[0]=tmp,CDQ(0,n);
	for(Re i=0;i<=n;++i)b[i]=ans[i];
}
int main(){
//    freopen("123.txt","r",stdin);
	in(n),--n;
	for(Re i=0;i<=n;++i)in(A[i]),A[i]%=P;
	polyinv(A,n,B);
	for(Re i=0;i<=n;++i)printf("%d ",B[i]);
}
字符串匹配 NTT
63 行
CPP JSON
【字符串匹配(NTT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 void get_next(无参数) — 获取值 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void sakura(Re *f,Re n,Re *g,Re m) — 后缀数组 关键配置: N=1048576+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=1048576+3,P=998244353,G=3;
int n,m,ans,invG,f[N],g[N],tr[N],S1[N],S2[N],PA[N],nex[N];char A[N],B[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void get_next(){
	for(Re i=2,j=0;i<=m;++i){
		while(j&&B[i]!=B[j+1])j=nex[j];
		if(B[i]==B[j+1])++j;nex[i]=j;
	}
	for(Re i=1;i<=m;++i)printf("%d ",nex[i]);
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
				base=(LL)base*w1%P;
			}
	}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
	for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%s%s",A+1,B+1),invG=inv(G);
	n=strlen(A+1),m=strlen(B+1);
	for(Re i=1;i<=n;++i)f[i]=A[n-i+1]-'A'+1,S1[i]=S1[i-1]+f[i]*f[i];
	for(Re i=1;i<=m;++i)g[i]=B[i]-'A'+1,S2[i]=S2[i-1]+g[i]*g[i];
	sakura(f,n,g,m);
	for(Re i=m;i<=n;++i)PA[n-i+1]=((S1[i]-S1[i-m]+S2[m])%P-2*f[i+1]%P+P)%P;
	for(Re i=1;i<=n-m+1;++i)if(PA[i]==0)printf("%d\n",i);
	get_next();
}
拉格朗日插值 x从0到n不连续
54 行
CPP JSON
【拉格朗日插值(x从0到n不连续)】 拉格朗日插值法模板,通过 n+1 个点确定 n 次多项式。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int Inv(Re x) — 求模逆元 void mul(Re *f,Re n,Re a0,Re *g) — 核心算法函数 void div(Re *g,Re n,Re a0,Re *f) — 核心算法函数 void Lagrange(Re *x,Re *y,Re n,Re *F) — 核心算法函数 关键配置: N=2003+3,P=998244353 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2003+3,P=998244353;
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int Inv(Re x){return mi(x,P-2);}
int ff[N],gg[N];
inline void mul(Re *f,Re n,Re a0,Re *g){
	for(Re i=0;i<=n;++i)ff[i]=f[i];
	g[0]=(LL)a0*ff[0]%P;for(Re i=1;i<=n+1;++i)g[i]=((LL)a0*ff[i]%P+ff[i-1])%P;
}
inline void div(Re *g,Re n,Re a0,Re *f){
	for(Re i=0;i<=n;++i)gg[i]=g[i];
	f[n-1]=gg[n];for(Re i=n-2;i>=0;--i)f[i]=(gg[i+1]-(LL)a0*f[i+1]%P+P)%P;
}
int fi[N],fmul[N];
inline void Lagrange(Re *x,Re *y,Re n,Re *F){
	fmul[0]=P-x[0],fmul[1]=1;
	for(Re i=1;i<=n;++i)mul(fmul,i,P-x[i],fmul);
	for(Re i=0;i<=n-1;++i)F[i]=0;
	for(Re i=0;i<=n;++i){
		Re tmp=1;
		for(Re j=0;j<=n;++j)if(i!=j)tmp=(LL)tmp*(x[i]-x[j]+P)%P;
		tmp=(LL)y[i]*Inv(tmp)%P;
		div(fmul,n+1,P-x[i],fi);
		for(Re i=0;i<=n;++i)(F[i]+=(LL)tmp*fi[i]%P)%=P;
	}
}
int n,X,ans,x[N],y[N],F[N];
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(X),--n;
	for(Re i=0;i<=n;++i)in(x[i]),in(y[i]);
	Lagrange(x,y,n,F);
	for(Re i=0,tmp=1;i<=n;++i)(ans+=(LL)F[i]*tmp%P)%=P,tmp=(LL)tmp*X%P;
	printf("%d\n",ans);
}
拉格朗日插值 x从0到n连续
56 行
CPP JSON
【拉格朗日插值(x从0到n连续)】 拉格朗日插值法模板,通过 n+1 个点确定 n 次多项式。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int Inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 关键配置: N=1048576+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1048576+3,P=998244353,G=3;
int jc[N],inv[N],invjc[N];
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int Inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[len+i]%P;
				f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
	}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);invG=Inv(G);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);Re invn=Inv(n);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int n,m,y[N],f[N],g[N],F[N];
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),jc[0]=jc[1]=inv[1]=invjc[0]=invjc[1]=1;
	for(Re i=2;i<=n;++i)inv[i]=(LL)inv[P%i]*(P-P/i)%P,jc[i]=(LL)jc[i-1]*i%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P;
	for(Re i=0;i<=n;++i)in(y[i]),g[i]=(LL)y[i]*((n-i&1)?P-1:1)%P*invjc[i]%P*invjc[n-i]%P;
	for(Re i=0;i<=(n<<1);++i)f[i]=Inv(m-n+i);
	times(f,n<<1,g,n);Re tmp=1;
	for(Re i=m-n;i<=m;++i)tmp=(LL)tmp*i%P;
	for(Re i=0;i<=n;tmp=(LL)tmp*Inv(m-n+i)%P,++i,tmp=(LL)tmp*(m+i)%P)F[i]=(LL)tmp*f[n+i]%P;
	for(Re i=m;i<=m+n;++i)printf("%d ",F[i-m]);
}
字符串匹配套路一:通配符 (NTT) 残缺的字符串
70 行
CPP JSON
【字符串匹配套路一:通配符 (NTT)(残缺的字符串)】 数论变换(NTT)模板,在模意义下计算多项式卷积,避免浮点误差。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void sakura(Re *f,Re n,Re *g,Re m) — 后缀数组 关键配置: N=524288+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 69 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=524288+3,P=998244353,G=3;
int n,m,ans,invG,a[N],b[N],f[N],g[N],tr[N],PA[N];char A[N],B[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
				base=(LL)base*w1%P;
			}
	}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
	for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(m),in(n),scanf("%s%s",B+1,A+1),invG=inv(G);
	for(Re i=1;i<=n/2;++i)swap(A[i],A[n-i+1]);
	for(Re i=1;i<=n;++i)a[i]=(A[i]=='*'?0:A[i]-'a'+1);
	for(Re i=1;i<=m;++i)b[i]=(B[i]=='*'?0:B[i]-'a'+1);
	for(Re i=1;i<=n;++i)f[i]=(LL)a[i]*a[i]%P*a[i]%P;
	for(Re i=1;i<=m;++i)g[i]=b[i];
	sakura(f,n,g,m);
	for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(Re i=1;i<=n;++i)f[i]=a[i];
	for(Re i=1;i<=m;++i)g[i]=(LL)b[i]*b[i]%P*b[i]%P;
	sakura(f,n,g,m);
	for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(Re i=1;i<=n;++i)f[i]=(LL)a[i]*a[i]%P;
	for(Re i=1;i<=m;++i)g[i]=(LL)b[i]*b[i]%P;
	sakura(f,n,g,m);
	for(Re i=m;i<=n;++i)(PA[n-i+1]+=P-2*f[i+1]%P)%=P;
	Re ans=0;
	for(Re i=1;i<=n-m+1;++i)ans+=(PA[i]==0);
	printf("%d\n",ans);
	for(Re i=1;i<=n-m+1;++i)if(PA[i]==0)printf("%d ",i);
}
字符串匹配套路二:较小字符集 (NTT) Fuzzy Search
63 行
CPP JSON
【字符串匹配套路二:较小字符集 (NTT)(Fuzzy Search)】 数论变换(NTT)模板,在模意义下计算多项式卷积,避免浮点误差。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void sakura(Re *f,Re n,Re *g,Re m) — 后缀数组 关键配置: N=262144+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,m,K,invG,a[N],b[N],f[N],g[N],S[N],tr[N],PA[N],id[200];char A[N],B[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
				base=(LL)base*w1%P;
			}
	}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
	for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(K),scanf("%s%s",A+1,B+1),invG=inv(G);
	id['A']=1,id['T']=2,id['C']=3,id['G']=4;
	for(Re i=1;i<=n;++i)a[i]=id[A[n-i+1]];
	for(Re i=1;i<=m;++i)b[i]=id[B[i]];
	for(Re o=1;o<=4;++o){
		for(Re i=1;i<=n;++i)S[i]=S[i-1]+(a[i]==o);
		for(Re i=1;i<=n;++i)f[i]=(S[i]-S[max(i-K-1,0)]||S[min(i+K,n)]-S[i-1]);
		for(Re i=1;i<=m;++i)g[i]=(b[i]==o);
		sakura(f,n,g,m);
		for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
		memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	}
	Re ans=0;
	for(Re i=1;i<=n-m+1;++i)ans+=(PA[i]==m);
	printf("%d\n",ans);
}
已复制