社区讨论
求助,有人知道我的eps为什么开到20000才过么
P4173残缺的字符串参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lq9hcmvy
- 此快照首次捕获于
- 2023/12/17 20:45 2 年前
- 此快照最后确认于
- 2023/12/17 23:31 2 年前
CPP
虽然某位学长在讨论区里提出过一样的问题,但是好像现在也没有结果(((
#include<bits/stdc++.h>
#define int long long
#define db double
using namespace std;
const int N=3e5+5;
const db pi=acos(-1);
struct comp{
db a,b;
comp(){
}
comp(db _a,db _b){
a=_a,b=_b;
}
friend comp operator+(comp x,comp y){
return comp(x.a+y.a,x.b+y.b);
}
friend comp operator-(comp x,comp y){
return comp(x.a-y.a,x.b-y.b);
}
friend comp operator*(comp x,comp y){
return comp(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);
}
};
int r,c,n;
bool vis[N<<2];
comp a[N<<2],b[N<<2],ans[N<<2];
void fft(comp *a,int len,int opt=1){
if(len==1)return;
comp* a0=new comp[len/2];
comp* a1=new comp[len/2];
for(int i=0;i<len;i+=2){
a0[i/2]=a[i];
a1[i/2]=a[i+1];
}
fft(a0,len>>1,opt);
fft(a1,len>>1,opt);
comp w=comp(1,0),w_n=comp(cos(2*pi/len),opt*sin(2*pi/len));
for(int i=0;i<len/2;++i){
a[i]=a0[i]+w*a1[i];
a[i+len/2]=a0[i]-w*a1[i];
w=w*w_n;
}
delete[]a0;
delete[]a1;
return;
}
string s1,s2;
double A[N<<2],B[N<<2];
void work(){
int n,m;
cin>>n>>m>>s1>>s2;
reverse(s1.begin(),s1.end());
for(int i=0;i<n;++i)A[i]=(s1[i]=='*')?0:(s1[i]-'a'+1);
for(int i=0;i<m;++i)B[i]=(s2[i]=='*')?0:(s2[i]-'a'+1);
int lim=1;
while(lim<=2*m)lim<<=1;
for(int i=0;i<=lim;++i)a[i]=comp(A[i]*A[i]*A[i],0);
for(int i=0;i<=lim;++i)b[i]=comp(B[i],0);
fft(a,lim,1);fft(b,lim,1);
for(int i=0;i<=lim;++i)ans[i]=ans[i]+a[i]*b[i];
for(int i=0;i<=lim;++i)a[i]=comp(A[i],0);
for(int i=0;i<=lim;++i)b[i]=comp(B[i]*B[i]*B[i],0);
fft(a,lim,1);fft(b,lim,1);
for(int i=0;i<=lim;++i)ans[i]=ans[i]+a[i]*b[i];
for(int i=0;i<=lim;++i)a[i]=comp(A[i]*A[i],0);
for(int i=0;i<=lim;++i)b[i]=comp(B[i]*B[i],0);
fft(a,lim,1);fft(b,lim,1);
for(int i=0;i<=lim;++i)ans[i]=ans[i]-a[i]*b[i]*comp(2,0);
fft(ans,lim,-1);
int cnt=0;
for(int i=s1.size()-1;i<s2.size();++i)if(abs(ans[i].a)<=20000)cnt++;
cout<<cnt<<'\n';
for(int i=s1.size()-1;i<s2.size();++i)if(abs(ans[i].a)<=20000)cout<<i-n+2<<' ';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;
// cin>>T;
while(T--)work();
return 0;
}
if(fabs(abs(ans[i].a))<20000)就是这一句话。。而且我样例都过不了还能水过去。。
回复
共 0 条回复,欢迎继续交流。
正在加载回复...