1 条题解

  • 0
    @ 2025-9-10 9:04:44

    C++ :

    #include <cstdio>
    #include <algorithm>
    #include <complex>
    
    using namespace std;
    
    typedef complex<double> Complex;
    #define LL long long
    const int MAXN = 1 << 18;
    
    const double PI = acos(-1.0);
    void FFT(Complex P[], int n, int oper)
    {
    	for (int i = 1, j = 0; i < n - 1; i++) {
    		for (int s = n; j ^= s >>= 1, ~j & s;);
    		if (i < j) swap(P[i], P[j]);
    	}
    	Complex unit_p0;
    	for (int d = 0; (1 << d) < n; d++) {
    		int m = 1 << d, m2 = m * 2;
    		double p0 = PI / m * oper;
    		unit_p0 = Complex(cos(p0), sin(p0));
    		for (int i = 0; i < n; i += m2) {
    			Complex unit = 1;
    			for (int j = 0; j < m; j++) {
    				Complex &P1 = P[i + j + m], &P2 = P[i + j];
    				Complex t = unit * P1;
    				P1 = P2 - t;
    				P2 = P2 + t;
    				unit = unit * unit_p0;				
    			}
    		}
    	}
    }
    
    int n;
    Complex x[MAXN], y[MAXN], z[MAXN], c[MAXN];
    
    inline double squ(double k)
    {
    	return k * k;
    }
    
    int main()
    {
        //freopen("force.in", "r", stdin);
        //freopen("force.out", "w", stdout);
    
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++)
    		scanf("%lf", &x[i]);
    	for (int i = 0; i < n; i++)
    		y[i] = -1.0 / squ(n - i);
    	y[n] = 0;
    	for (int i = n + 1; i <= 2 * n; i++)
    		y[i] = 1.0 / squ(i - n);
    		
    	int MXN = 1;
    	while (MXN < n * 2 + 1)
    		MXN *= 2;
    	//printf("%d\n", MXN);
    	for (int i = n; i < MXN; i++)
    	    x[i] = 0;
    	for (int i = 2 * n + 1; i < MXN; i++)
    	    y[i] = 0;
    	    
    	FFT(x, MXN, 1);
    	FFT(y, MXN, 1);
    	for (int i = 0; i < MXN; ++i)
    		z[i] = x[i] * y[i];
    	FFT(z, MXN, -1);
    	for (int i = 0; i < MXN; ++i)
    		c[i] = z[i].real() / MXN;
    	for (int i = 0; i < n; i++)
    		printf("%.3f\n", c[n + i].real());
    	
    	return 0;
    }
    
    
    • 1

    信息

    ID
    3722
    时间
    3000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者