P4173 残缺的字符串 FFT求调
  • 板块学术版
  • 楼主zhengzidu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/17 11:51
  • 上次更新2024/7/17 13:59:34
查看原帖
P4173 残缺的字符串 FFT求调
954640
zhengzidu楼主2024/7/17 11:51
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0;
	short f=1;
	char c=getchar();
	while(c>57||c<48){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c<58&&c>47){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0ll) putchar(45),x=~x+1;
	if(x>9ll) write(x/10);
	putchar(x%10|48);
}
const double pi=acos(-1.0);
int n,m,limit,bit;
struct fast_fourier_transform_recursion{
	struct complexs{
	    double x,y;
		complexs(double xx=0,double yy=0){
			x=xx,y=yy;
		}
	}f[200001],g[200001];
	friend complexs operator+(complexs a,complexs b){ 
		return complexs(a.x+b.x,a.y+b.y);
	}
	friend complexs operator-(complexs a,complexs b){ 
		return complexs(a.x-b.x,a.y-b.y);
	}
	friend complexs operator*(complexs a,complexs b){ 
		return complexs(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
	}
	void fft(int limit,complexs *f,int op){
		if(limit==1){
			return;
		}
		complexs a1[limit>>1|7],a2[limit>>1|7];
		for(int i=0;i<limit;i+=2){
			a1[i>>1]=f[i];
			a2[i>>1]=f[i+1];
		}
		fft(limit>>1,a1,op);
		fft(limit>>1,a2,op);
		complexs omega=complexs(cos(2.0*pi/limit),op*sin(2.0*pi/limit));
		complexs w=complexs(1,0);
		for(int i=0;i<(limit>>1);i++,w=w*omega){
			f[i]=a1[i]+w*a2[i];
			f[i+(limit>>1)]=a1[i]-w*a2[i];
		}
	}
	void work(){
		limit=1;
		while(limit<=n+m){
			limit<<=1;
		}
		fft(limit,f,1);
		fft(limit,g,1);
		for(int i=0;i<limit;i++){
			f[i]=f[i]*g[i];
		}
		fft(limit,f,-1);
		}
}fft1;
struct fast_fourier_transform_iteration{
	int rev[2000010];
	struct complexs{
	    double x,y;
		complexs(double xx=0,double yy=0){
			x=xx,y=yy;
		}
	}f[2000010],g[2000010];
	friend complexs operator+(complexs a,complexs b){ 
		return complexs(a.x+b.x,a.y+b.y);
	}
	friend complexs operator-(complexs a,complexs b){ 
		return complexs(a.x-b.x,a.y-b.y);
	}
	friend complexs operator*(complexs a,complexs b){ 
		return complexs(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
	}
	void fft(complexs *f,int limit,double op){
		for(int i=0;i<limit;i++){
			if(i<rev[i]){
				swap(f[i],f[rev[i]]);
			}
		}
		for(int mid=1;mid<limit;mid<<=1){
			complexs omega(cos(pi/mid),op*sin(pi/mid));
			for(int j=0;j<limit;j+=(mid<<1)){
				complexs w(1,0);
				for(int l=0;l<mid;l++,w=w*omega){
					complexs x=f[l+j];
					complexs y=w*f[l+j+mid];
					f[l+j]=x+y;
					f[l+j+mid]=x-y; 
				}
			}
		}
	}
	void work(){
		limit=1;
		while(limit<=n+m){
			limit<<=1;
			bit++;
		}
		for(int i=0;i<=limit;i++){
			rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		}
		fft(f,limit,1);
		fft(g,limit,1);
		for(int i=0;i<=limit;i++){
			f[i]=f[i]*g[i];
		}
		fft(f,limit,-1);
	}
}fft2;
#define mod 998244353
struct ntt_mod998244353{
	int rev[400001],inv,f[400001],g[400001];
	long long qckpow(long long a,long long b){
		long long sum=1;
		long long base=a; 
		while(b!=0){
			if(b%2==1){
				sum=(sum*base)%mod; 
			}
			base=(base*base)%mod; 
			b/=2;
		}
		return sum;
	}
	void ntt(int *f,int op){
		for(int i=0;i<limit;i++){
			if(i<rev[i]){
				swap(f[i],f[rev[i]]);
			}
		}
		for(int mid=1;mid<limit;mid<<=1){
			int omega=qckpow(op==1?3:332748118,(mod-1)/(mid<<1));
			for(int j=0;j<limit;j+=(mid<<1)){
				int w=1;
				for(int k=0;k<mid;k++,w=(w*omega)%mod){
					int x=f[j+k];
					int y=w*f[j+k+mid]%mod;
					f[j+k]=(x+y)%mod;
					f[j+k+mid]=(x-y+mod)%mod;
				}
			}
		}
	}
	void work(){
		limit=1;
		while(limit<=n+m){
			limit<<=1;
			++bit;
		}
		for(int i=0;i<limit;i++){
			rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		}
		ntt(f,1);
		ntt(g,1);
		for(int i=0;i<limit;i++){
			f[i]=(f[i]*g[i])%mod;
		}
		ntt(f,-1);
		inv=qckpow(limit,mod-2);
	}
}ntt1;
char s[300010],t[300010];
vector<int> ans;
signed main(){
	m=read();
	n=read();
	for(int i=0;i<=m-1;i++){
		cin>>t[i];
		if(t[i]=='*'){
			fft2.g[m-i].x=0;
		}
		else{
			fft2.g[m-i].x=(double)((double)1.000/double((double)10001.000+double(t[i]-'a')));
		}
	}
	for(int i=0;i<=n-1;i++){
		cin>>s[i];
		if(s[i]=='*'){
			fft2.f[i+1].x=0;
		}
		else{
			fft2.f[i+1].x=(10001.0+double(s[i]-'a'));
		}
	}
	limit=1;
	while(limit<=n+m){
		limit<<=1;
		bit++;
	}
	for(int i=0;i<limit;i++){
		fft2.rev[i]=(fft2.rev[i>>1]>>1)|((i&1)<<(bit-1));
	}
	fft2.fft(fft2.f,limit,1);
	fft2.fft(fft2.g,limit,1);
	for(int i=0;i<=limit;i++){
		fft2.f[i]=fft2.f[i]*fft2.g[i];
	}
	fft2.fft(fft2.f,limit,-1);
	for(int i=m+1;i<=n+1;i++){
		fft2.f[i].x/=(double)limit;
		int res=(int)(fft2.f[i].x+0.5);
		if(abs(fft2.f[i].x-(double(res)))<=1e-5){
			ans.push_back(i-m);
		}
	}
    write(ans.size());
    printf("\n");
    for(int i=0;i<ans.size();i++){
    	write(ans[i]);
    	printf(" ");
	}
	return 0;
}

record

2024/7/17 11:51
加载中...