[UVA 12633] Super Rooks on Chessboard

UVA 12633

思路

考虑求出每个对角线上没有被行列覆盖过的格子,再将所有未覆盖的对角线的格子数加起来,很显然是卷积形式,可以FFT

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

typedef long long LL;
const int MAXN=50010, MX=(1<<17)+10;
const double Pi=3.1415926535897;
int R, C, r[MAXN], c[MAXN], a[MX], b[MX], qwq[MX];
bool visd[MAXN*2];

namespace FFT{
    struct Complex{
        double x, y;
        Complex(double x=0, double y=0) : x(x), y(y){}
        Complex operator +(Complex _){return Complex(x+_.x, y+_.y);}
        Complex operator -(Complex _){return Complex(x-_.x, y-_.y);}
        Complex operator *(Complex _){return Complex(x*_.x-y*_.y, x*_.y+y*_.x);}
    }A[MX], B[MX];
    int n, rev[MX];
    
    void fft(Complex *P, int opt){
        for(int i=0; i<n; i++) if(rev[i]>i)
            std::swap(P[rev[i]], P[i]);
        for(int i=1; i<n; i<<=1){
            Complex W=Complex(cos(Pi/i), sin(Pi/i)*opt);
            for(int p=i<<1, j=0; j<n; j+=p){
                Complex w=Complex(1, 0);
                for(int k=0; k<i; k++, w=w*W){
                    Complex X=P[j+k], Y=P[i+j+k]*w;
                    P[j+k]=X+Y, P[i+j+k]=X-Y;
                }
            }
        }
    }
    
    void conv(int *x, int *y, int *ans, int len){
        n=1; while(n<=2*len) n<<=1;
        for(int i=0; i<n; i++) 
            rev[i]=(rev[i>>1]>>1) | ((i&1) ? n>>1 : 0);
        for(int i=0; i<n; i++)
            A[i]=Complex(x[i], 0), B[i]=Complex(y[i], 0);
        fft(A, 1); fft(B, 1);
        for(int i=0; i<n; i++) A[i]=A[i]*B[i];
        fft(A, -1);
        for(int i=0; i<n; i++) ans[i]=int(A[i].x/n+0.5);
    }
}

int main(){
    int T, N;
    scanf("%d", &T);
    for(int _=1; _<=T; _++){
        scanf("%d%d%d", &R, &C, &N);
        memset(visd, 0, sizeof(visd));
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for(int i=1; i<=R; i++) a[i]=1;
        for(int i=1; i<=C; i++) b[i]=1; 
        for(int i=1; i<=N; i++){
            scanf("%d%d", &r[i], &c[i]);
            a[r[i]]=0; b[C-c[i]+1]=0;
            visd[r[i]+C-c[i]+1]=true;
        }
        LL ans=0;
        FFT::conv(a, b, qwq, std::max(R, C));
        for(int i=0; i<=R+C; i++) if(!visd[i])
            ans+=1LL*qwq[i];
        printf("Case %d: %lld\n", _, ans);
    }
    return 0;
}

发表评论

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