[母函数][容斥][FFT] UVa 12633 Super Rooks on Chessboard

一开始看了很久不知道怎么求被对角线覆盖到而没有被横纵覆盖到的格子数,后来忽然发现可以把没被占用的横纵坐标标记为1啊!这样两个卷积起来就是没有被横纵占用的对角线上的格子数量了!!!然后遍历每条对角线,如果被覆盖到了就减去这上面没有被横纵覆盖到的格子!

wa点:日常LL,以及他这个操蛋的横纵坐标标识法,有点难受,得把棋盘左右反转一下才好做。

#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)
{
    register 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;i
	

发表评论

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

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