自动搬运

查看原文

来自洛谷，原作者为

	ax_by_c ZJOI

搬运于2025-08-24 23:06:13，当前版本为作者最后更新于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;
}