社区讨论

你说的对,但__

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]);
}
它们唯一的不同只有代码第4040行我的bb数组的赋值上界,但第一份错误,连样例都过不了,差的挺大的
这里我的有关答案的下标都是n≤n的,为什么我多赋值n+1limn+1−lim是错的?
有没有大神回复

回复

11 条回复,欢迎继续交流。

正在加载回复...