[母函数][容斥][FFT][模板] SPOJ TSUM Triple Sums

https://cn.vjudge.net/problem/SPOJ-TSUM

跟焦作选拔的时候那个题目的思路完全一样,用母函数可以考虑到所有的情况,然后去掉三个重复的和两个重复的再除以6就得到了去重后的结果。

收获主要是发现了FFT那个乘法的操作可以全部在一次循环里完成。。。神奇。。还有就是移位操作可以避免复数,而输出的时候记着要移回去原位。

#include

using namespace std;
typedef long long LL;
const int maxn=(1<<17);
const int mod=998244353;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

struct Complex
{
    double x,y;
    Complex(double _x=0.0,double _y=0.0)
    {
        x=_x,y=_y;
    }
    Complex operator-(const Complex &b)const
    {
        return Complex(x-b.x,y-b.y);
    }
    Complex operator +(const Complex &b)const
    {
        return Complex(x+b.x,y+b.y);
    }
    Complex operator *(const Complex &b)const
    {
        return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
    }
};

void change(Complex y[],int len)
{
     int i,j,k;
    for(i=1,j=(len>>1);i>1);
        while(j>=k)
        {
            j-=k;
            k>>=1;
        }
        if(j>1);k++)
            {
                u=y[k];
                t=w*y[k+(h>>1)];
                y[k]=u+t;
                y[k+(h>>1)]=u-t;
                w=w*wn;
            }
        }
    }
    if(on==-1)
    {
        for(int i=0;i0)
        {
            printf("%d : %lld\n",i-60000,ans);
        }
    }
    return 0;
}


发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据