社区讨论
你说的对,但__
P3338[ZJOI2014] 力参与者 2已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mi7m8hay
- 此快照首次捕获于
- 2025/11/20 23:58 4 个月前
- 此快照最后确认于
- 2025/11/21 01:12 4 个月前
以下是我的两份代码
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Cl
{
double x,y;
friend Cl operator +(Cl a,Cl b){return (Cl){a.x+b.x,a.y+b.y};}
friend Cl operator -(Cl a,Cl b){return (Cl){a.x-b.x,a.y-b.y};}
friend Cl operator *(Cl a,Cl b){return (Cl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
}a[400005],b[400005];
const double Pi=acos(-1.0);
int r[400005],t,lim=1;
double ans[400005],cs[400005];
void FFT(Cl *a,int ty)
{
for(int i=0;i<lim;i++)
{
if(r[i]<i) swap(a[i],a[r[i]]);
}
for(int i=2;i<=lim;i*=2)
{
for(int j=0;j<lim;j+=i)
{
Cl W=(Cl){cos(2.0*Pi/i),ty*sin(2.0*Pi/i)},w=(Cl){1.0,0.0};
for(int k=0;k<(i>>1);k++,w=w*W)
{
Cl x=a[j+k],y=a[j+k+(i>>1)]*w;
a[j+k]=x+y,a[j+k+(i>>1)]=x-y;
}
}
}
}
signed main()
{
int n;
scanf("%lld",&n);
for(int i=0;i<lim;i++) a[i].x=a[i].y=0,b[i].x=b[i].y=0;
for(int i=1;i<=n;i++) scanf("%lf",&cs[i]),a[i].x=cs[i];
while(lim<2*n) lim*=2,t++;
for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(t-1));
for(int i=1;i<lim;i++) b[i].x=1.0/i/i,b[i].y=0.0;
FFT(a,1),FFT(b,1);
for(int i=0;i<lim;i++) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=1;i<=n;i++) ans[i]=a[i].x/lim;
for(int i=0;i<lim;i++) a[i].x=a[i].y=0;
for(int i=1;i<=n;i++) a[i].x=cs[n-i+1];
FFT(a,1);
for(int i=0;i<lim;i++) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=1;i<=n;i++) ans[i]-=a[n-i+1].x/lim,printf("%.3lf\n",ans[i]);
}
CPP#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Cl
{
double x,y;
friend Cl operator +(Cl a,Cl b){return (Cl){a.x+b.x,a.y+b.y};}
friend Cl operator -(Cl a,Cl b){return (Cl){a.x-b.x,a.y-b.y};}
friend Cl operator *(Cl a,Cl b){return (Cl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
}a[400005],b[400005];
const double Pi=acos(-1.0);
int r[400005],t,lim=1;
double ans[400005],cs[400005];
void FFT(Cl *a,int ty)
{
for(int i=0;i<lim;i++)
{
if(r[i]<i) swap(a[i],a[r[i]]);
}
for(int i=2;i<=lim;i*=2)
{
for(int j=0;j<lim;j+=i)
{
Cl W=(Cl){cos(2.0*Pi/i),ty*sin(2.0*Pi/i)},w=(Cl){1.0,0.0};
for(int k=0;k<(i>>1);k++,w=w*W)
{
Cl x=a[j+k],y=a[j+k+(i>>1)]*w;
a[j+k]=x+y,a[j+k+(i>>1)]=x-y;
}
}
}
}
signed main()
{
int n;
scanf("%lld",&n);
for(int i=0;i<lim;i++) a[i].x=a[i].y=0,b[i].x=b[i].y=0;
for(int i=1;i<=n;i++) scanf("%lf",&cs[i]),a[i].x=cs[i];
while(lim<2*n) lim*=2,t++;
for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(t-1));
for(int i=1;i<=n;i++) b[i].x=1.0/i/i,b[i].y=0.0;
FFT(a,1),FFT(b,1);
for(int i=0;i<lim;i++) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=1;i<=n;i++) ans[i]=a[i].x/lim;
for(int i=0;i<lim;i++) a[i].x=a[i].y=0;
for(int i=1;i<=n;i++) a[i].x=cs[n-i+1];
FFT(a,1);
for(int i=0;i<lim;i++) a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=1;i<=n;i++) ans[i]-=a[n-i+1].x/lim,printf("%.3lf\n",ans[i]);
}
它们唯一的不同只有代码第行我的数组的赋值上界,但第一份错误,连样例都过不了,差的挺大的
这里我的有关答案的下标都是的,为什么我多赋值是错的?
有没有大神回复
回复
共 11 条回复,欢迎继续交流。
正在加载回复...