题解：P11302 [NOISG 2021 Finals] Tiles

ax_by_c · 2025-03-20 19:28:26 · 题解

令 m 表示行数，本题中 m=3。

思考暴力怎么做，考虑 DP。

设 f_{i,S} 表示铺完前 i 列内部的瓷砖且第 i 列已经不能铺设的位置集合为 S 的方案数。

转移枚举横向瓷砖铺设情况与下一列纵向瓷砖铺设情况即可，单次时间复杂度 O(n2^m)。

显然转移只和每一列的黑白情况有关，于是考虑 ddp，预处理每一种黑白情况对应的转移矩阵即可。

时间复杂度 O(8^m(n+q)\log n)。

#include<bits/stdc++.h>
using namespace std;
namespace ax_by_c{
typedef long long ll;
const ll mod=1e9+7;
const int N=3e4+5;
const int S=8;
struct matr{
    int n,m,a[S][S];
    void clr(){
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)a[i][j]=0;
    }
}ms[S],ss;
matr __c;
matr operator * (const matr &a,const matr &b){
    __c.n=a.n,__c.m=b.m,__c.clr();
    for(int i=0;i<a.n;i++)
    for(int j=0;j<a.m;j++)
    for(int k=0;k<b.m;k++)__c.a[i][k]=(__c.a[i][k]+(ll)a.a[i][j]*b.a[j][k])%mod;
    return __c;
}
struct seg{
    matr tr[N*4];
    void pu(int u){
        tr[u]=tr[u<<1]*tr[u<<1|1];
    }
    void upd(int u,int l,int r,int p,int v){
        if(l==r){
            tr[u]=ms[v];
            return ;
        }
        int mid=l+((r-l)>>1);
        if(p<=mid)upd(u<<1,l,mid,p,v);
        else upd(u<<1|1,mid+1,r,p,v);
        pu(u);
    }
    matr Q(int u,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return tr[u];
        int mid=l+((r-l)>>1);
        if(qr<=mid)return Q(u<<1,l,mid,ql,qr);
        if(mid+1<=ql)return Q(u<<1|1,mid+1,r,ql,qr);
        return Q(u<<1,l,mid,ql,qr)*Q(u<<1|1,mid+1,r,ql,qr);
    }
}tr;
int n,q,a[N];
char s[5][N];
void main(){
    for(int s=0;s<S;s++){
        ms[s].n=ms[s].m=S,ms[s].clr();
        for(int i=0;i<S;i++){
            for(int j=0;j<S;j++){
                if((j&(i^(S-1)))==j&&(j&s)==0){
                    int x=j|s;
                    ms[s].a[i][x]++;
                    if(!(x&3))ms[s].a[i][x|3]++;
                    if(!(x&6))ms[s].a[i][x|6]++;
                }
            }
        }
    }
    scanf("%d %d %s %s %s",&n,&q,s[1]+1,s[2]+1,s[3]+1);
    for(int i=1;i<=n;i++)a[i]=((s[3][i]=='x')<<2)|((s[2][i]=='x')<<1)|(s[1][i]=='x');
    for(int i=1;i<=n;i++)tr.upd(1,1,n,i,a[i]);
    for(int i=1,op,x,y;i<=q;i++){
        scanf("%d %d %d",&op,&x,&y);
        if(op==1)a[y]^=1<<(x-1),tr.upd(1,1,n,y,a[y]);
        if(op==2){
            ss.n=1,ss.m=S,ss.clr();
            ss.a[0][S-1]++;
            ss=ss*tr.Q(1,1,n,x,y);
            int ans=0;
            for(int j=0;j<S;j++)ans=(ans+ss.a[0][j])%mod;
            printf("%d\n",ans);
        }
    }
}
}
int main(){
    ax_by_c::main();
    return 0;
}