P6407 [SDOI2012] 棋盘覆盖

type A

直接跑二分图匹配。

type B

猜结论：一定能铺满。
考虑分治，每次将矩阵平均分成 \(4\) 份，每一份一样大，考虑放一个块覆盖祂们中的 \(3\) 个格子。只要每次都把空的格子留给已经有障碍的矩形，那么在递归时每个矩形都恰好有一个障碍，当分治到 \(2\times2\) 后就结束了，所以一定有方法可以铺满。
那么现在需要实现两个大整数乘法，用 \(FFT\)。

type C

考虑状压。用逐格 \(DP\)，把前两行都压进来，转移时要注意边界。
这样做时间复杂度为 \(\mathcal O(2^{2m}\times nm)\)，理论不能过，但是跑不满，手写哈希表优化一下就能过了。

代码

/*
Luogu P6407 [SDOI2012] 棋盘覆盖
2026-03-12
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
string N,M;
int k,n,m;
char op;
namespace type_A{
    template<int maxn,int maxm>class LSQXX{
    public:
        int head[maxn],nxt[maxm*2],to[maxm*2],val[maxm*2],cnt=1;
        void add(int u,int v,int w){nxt[++cnt]=head[u],to[cnt]=v,val[cnt]=w,head[u]=cnt;}
    };
    const int maxn=110,inf=1000000000;
    int bh[maxn][maxn],fx[10]={0,0,0,1,-1},fy[10]={0,1,-1};
    bool flag[maxn][maxn];
    class Network_Flow{
    private:
        LSQXX<maxn*maxn,maxn*maxn*10>e;
        int s,t,d[maxn*maxn],cur[maxn*maxn];
        void edge_add(int u,int v,int w){e.add(u,v,w),e.add(v,u,0);}
        bool bfs(){
            for(int i=s;i<=t;i++) d[i]=inf;
            queue<int>q;q.push(s);d[s]=0;
            while(!q.empty()){
                int u=q.front();q.pop();
                for(int i=e.head[u];i;i=e.nxt[i]){
                    int v=e.to[i];
                    if(e.val[i]==0) continue;
                    if(d[v]>d[u]+1) d[v]=d[u]+1,q.push(v);
                }
            }
            return d[t]!=inf;
        }
        int dfs(int u,int flow=inf){
            if(flow==0) return 0;
            if(u==t) return flow;
            int ans=0;
            for(int&i=cur[u];i;i=e.nxt[i]){
                int v=e.to[i];
                if(d[v]!=d[u]+1) continue;
                if(e.val[i]==0) continue;
                int new_flow=dfs(v,min(flow,e.val[i]));
                flow-=new_flow,ans+=new_flow;
                e.val[i]-=new_flow,e.val[i^1]+=new_flow;
                if(flow==0) return ans;
            }
            return ans;
        }
    public:
        void build(){
            for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) bh[i][j]=++t;
            t++;
            for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
                if(flag[i][j]) continue;
                if(i+j&1){edge_add(bh[i][j],t,1);continue;}
                edge_add(s,bh[i][j],1);
                for(int w=1;w<=4;w++){
                    int x=i+fx[w],y=j+fy[w];
                    if(x<1||x>n||y<1||y>m) continue;
                    if(flag[x][y]) continue;
                    edge_add(bh[i][j],bh[x][y],1);
                }
            }
        }
        int work(){
            int ans=0;
            while(bfs()){
                for(int i=s;i<=t;i++) cur[i]=e.head[i];
                ans+=dfs(s);
            }
            return ans;
        }
    }wll;
    void solve(){
        for(int i=1;i<=k;i++){
            int x,y;read(x,y);
            flag[x][y]=1;
        }
        wll.build();
        write(wll.work());
    }
};
namespace type_B{
    #define C complex<double>
    const double PI=3.14159265358979323846;
    const int maxn=300000;
    C a[maxn],b[maxn];
    int n,m,ans[maxn];
    void FFT(C a[],int n,bool flag){
        if(n==1) return ;
        C a0[n/2],a1[n/2];
        for(int i=0;i<n/2;i++) a0[i]=a[i*2],a1[i]=a[i*2+1];
        FFT(a0,n/2,flag),FFT(a1,n/2,flag);
        C w=1,dwg;
        if(flag) dwg.real(cos(-2*PI/n)),dwg.imag(sin(-2*PI/n));
        else dwg.real(cos(2*PI/n)),dwg.imag(sin(2*PI/n));
        for(int i=0;i<n/2;i++){
            a[i]=a0[i]+a1[i]*w;
            a[i+n/2]=a0[i]-a1[i]*w;
            w*=dwg;
        }
    }
    void mul(C a[],int n,C b[],int m){
        int len=1<<__lg(n+m)+1;
        FFT(a,len,0),FFT(b,len,0);
        for(int i=0;i<len;i++) a[i]*=b[i];
        FFT(a,len,1);
        for(int i=0;i<len;i++) a[i]/=len;
    }
    void solve(){
        for(int i=N.size()-1;~i;i--) a[n++]=N[i]-'0';
        for(int i=M.size()-1;~i;i--) b[m++]=M[i]-'0';
        mul(a,n-1,b,m-1);
        for(int i=0;i<=n+m+5;i++) ans[i]=round(a[i].real());
        for(int i=0;i<=n+m+5;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
        int nw=0;
        for(int i=n+m+5;i>=0;i--){
            nw*=10;
            ans[i]+=nw;
            nw=ans[i]%3;
            ans[i]/=3;
        }
        int zgw=n+m+5;
        while(!ans[zgw]) zgw--;
        for(int i=zgw;~i;i--) write(ans[i]);
    }
};
namespace type_C{
	struct HashTable{
		static const int MOD=299989;
		int head[MOD],nxt[(1<<22)+10],state[(1<<22)+10],val[(1<<22)+10],sz;
		void clear(){memset(head, 0, sizeof(head));sz=0;}
		void insert(int s,int v){
			int u=s%MOD;
			for(int i=head[u];i;i=nxt[i]) if(state[i] == s){val[i]=max(val[i],v);return;}
			++sz;
			state[sz]=s;
			val[sz]=v;
			nxt[sz]=head[u];
			head[u]=sz;
		}
	}h[2];
    const int maxn=20;
    bool flag[maxn][maxn];
    queue<tuple<int,int,int>>q;
    int get(int st,int w){return !!(st&(1<<w-1));}
    void update(int&st,int w,int z){
        if(z) st|=(1<<w-1);
        else st&=(1<<w-1);
    }
    void solve(){
        for(int i=1;i<=k;i++){
            int x,y;read(x,y);
            flag[x][y]=1;
        }
        int ans=0;
		int now=0,nxt=1;
		h[now].insert(0,0);
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
			h[nxt].clear();
			for(int k=1;k<=h[now].sz;k++){
				int s=h[now].state[k],v=h[now].val[k];
				auto insert=[i,j,v,nxt](int st,int z){h[nxt].insert(st,z+v);};
                s>>=1;
                if(flag[i][j]){
                    update(s,2*m+1,1);
                    insert(s,0);
                    continue;
                }
                int now_w=2*m+1;
                int st_up=get(s,now_w-m),st_up2=get(s,1),st_le=get(s,now_w-1),st_le2=get(s,now_w-2);
                int up=now_w-m,up2=1,le=now_w-1,le2=now_w-2;
                {
                    int new_s=s;
                    insert(new_s,0);
                }
                if(i>=3&&!st_up&&!st_up2){
                    int new_s=s;
                    update(new_s,up,1),update(new_s,up2,1),update(new_s,now_w,1);
                    insert(new_s,1);
                }
                if(j>=3&&!st_le&&!st_le2){
                    int new_s=s;
                    update(new_s,le,1),update(new_s,le2,1),update(new_s,now_w,1);
                    insert(new_s,1);
                }
                if(i>=2&&j<=m-1&&!st_up&&!get(s,up+1)){
                    int new_s=s;
                    update(new_s,up,1),update(new_s,up+1,1),update(new_s,now_w,1);
                    insert(new_s,1);
                }
                if(i>=2&&j>=2&&!st_up&&!get(s,up-1)){
                    int new_s=s;
                    update(new_s,up,1),update(new_s,up-1,1),update(new_s,now_w,1);
                    insert(new_s,1);
                }
                if(i>=2&&j>=2&&!st_le&&!get(s,up-1)){
                    int new_s=s;
                    update(new_s,le,1),update(new_s,up-1,1),update(new_s,now_w,1);
                    insert(new_s,1);
                }
                if(i>=2&&j>=2&&!st_le&&!st_up){
                    int new_s=s;
                    update(new_s,le,1),update(new_s,up,1),update(new_s,now_w,1);
                    insert(new_s,1);
                }
			}
			swap(now,nxt);
		}
        for(int i=1;i<=h[now].sz;i++) ans=max(ans,h[now].val[i]);
        write(ans);
    }
};
signed main(){
    read(M,N,k,op);
    if(op=='A'){
        for(int i:N) n=n*10+i-'0';
        for(int i:M) m=m*10+i-'0';
        type_A::solve();
        return 0;
    }
    if(op=='B'){
        type_B::solve();
        return 0;
    }
    for(int i:N) n=n*10+i-'0';
    for(int i:M) m=m*10+i-'0';
    type_C::solve();
    return 0;
}