萌新求助fft,过了样例WA了/kk
查看原帖
萌新求助fft,过了样例WA了/kk
220426
血色黄昏楼主2021/5/9 09:22

有神仙帮忙看一下吗/kk

#include<bits/stdc++.h>
using namespace std;
long long n, lim, kal, tr[3000012];
const double pi = acos(-1.0);
struct Complex{
	double x,y;
	Complex(double _x,double _y){x=_x,y=_y;} Complex(){x=y=0;}
	Complex operator +(Complex b){
		return Complex(x+b.x,y+b.y);
	}
	Complex operator -(Complex b){
		return Complex(x-b.x,y-b.y);
	}
	Complex operator *(Complex b){
		return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
	}
}f[3000010],g[3000010], ans[3000010], z[3000010];
void pre(int n)
{
    int high = 0;
    lim = 1;
    while(lim <= n)lim <<= 1, high ++;
    for(int i = 0;i < lim;i++)tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (high - 1));  
}
void fft(int lim, Complex *f,int dft)
{
    for(int i = 0;i < lim;i ++)if(i < tr[i])swap(f[i], f[tr[i]]);
    for(int p = 2;p <= lim;p <<= 1)
	{
		int len = (p >> 1);
        Complex wn = (Complex){cos(dft * 2 * pi / p),sin(dft*2*pi/p)};
        for(int k = 0;k < lim;k += p)
		{
            Complex buf = (Complex){1, 0};
            for(int i = k;i < k + len;i ++,buf = buf * wn)
			{
                Complex x, y;
                x = f[i], y = buf * f[i + len];
                f[i] = x + y;
                f[i + len] = x-y;
            }
        }
    }
    if(dft == -1)for(int i = 0;i < lim;i ++)f[i].x /= lim;
}
//void fft(int n, Complex *f, int flag)
//{
//	for(int i = 0;i < n;i ++)if(i < tr[i])swap(f[i], f[tr[i]]);
//	for(int p = 2;p <= n;p <<= 1)
//	{
//		int len = (p >> 1);
//		Complex wn(cos(2 * pi / p), sin(2 * pi / p));
//		if(flag = -1)wn.x *= -1, wn.y *= -1;
//		for(int k = 0;k < n;k += p)
//		{
//			Complex buf(1, 0);
//			for(int i = k;i < k + len;i ++,buf = buf * wn)
//			{
//				Complex tmp = buf * f[i + len];
//				f[i + len] = f[i] - tmp;
//				f[i] = f[i] + tmp;
//			}
//		}
//	}
//	if(flag == -1)for(int i = 0;i < n;i ++)f[i].x /= n;
//}
int main()
{
    scanf("%lld", &n);
    for(int i = 0;i < n;i ++)
	{
		scanf("%lld", &kal);
		kal += 2e4;
		f[kal].x ++;
		g[kal * 2].x ++;
		z[kal * 3].x ++;
	}
	pre((1<<17)-1);
	fft(lim, f, 1);
	fft(lim, g, 1);
	fft(lim, z, 1);
    for(int i = 0;i < lim;i ++)ans[i] = f[i] * (f[i] * f[i] - g[i] - g[i] - g[i]) + Complex{2, 0} * z[i];
    fft(lim, ans, -1);
	for(int i = 0;i < lim;i ++)
	{
		long long d = (long long)(ans[i].x + 0.49) / 6;
		if(d > 0)printf("%lld : %lld\n", i - 60000, d);
	}
	return 0;
}

2021/5/9 09:22
加载中...