专栏文章

P6557 题解

llmh_qwq
P6557题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mir26y12
此快照首次捕获于
2025/12/04 14:32
3 个月前
此快照最后确认于
2025/12/04 14:32
3 个月前
查看原文
两种放置人的情况被认为是不相同的，当且仅当两种情况人数不同或者存在一个编号相同的人射程范围内的格子中至少有一个格子编号不同，其中编号按照射程范围内的编号最小的格子的编号为关键字进行排序。也就是说，实际上这个人在哪里不重要，重要的是这个人的射程范围是多少。
因此，我们可以将题目转化为：在棋盘中放多个 1×k1\times k 或 k×1(k≥2)k\times 1(k\ge 2)，使得矩形两两不交的方案数。
这里我们使用轮廓线 dp，定义 fi,j,s,tf_{i,j,s,t} 为：
  1. 处理了所有左上角横坐标 <i<i 或横坐标 =i=i 且纵坐标 ≤j\le j 的矩形；
  2. 如果 ss 二进制表示第 kk 位（从低到高）为 11，则存在一个矩形同时包含 (i−[k>i],k)(i-[k>i],k) 和 (i−[k>i]+1,k)(i-[k>i]+1,k)；
  3. 如果 tt 为 11，则存在一个矩形同时包含 (i,j)(i,j) 和 (i,j+1)(i,j+1)。
或者说，我们用 s,ts,t 保存了 m+1m+1 个“插头”的状态。转移时需要注意判断不能让纵向和横向的插头撞上。
图中 n=m=7,i=j=4n=m=7,i=j=4，红色插头为 ss 保存的状态，绿色插头为 tt 保存的状态。
这样我们就解决了 T=0T=0 的情况，现在考虑如何解决询问。
如果 opt=2opt=2，那么我们删掉了一整行，把原来的网格图分成两个小网格图。这启发我们对每个“前缀”和“后缀”保存答案，需要的时候直接乘起来。opt=3opt=3 同理。
如果 opt=1opt=1，那么我们考虑 (x,y)(x,y) 的上一格和下一格的前（后）缀状态，发现它们的第 yy 个插头和插头 tt 都必须为 00，其他插头的状态必须对应相等。（可以理解为把两个长方形融合成一个，或者选择断开）
opt=4,5opt=4,5 的状态同理，需要把网格图沿对角线翻转再做一遍 dp。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=17,MOD=998244353;
int T,n,m,a[N][N],f[N][N][1<<15][2],g[N][N][1<<15][2],ans[1007];
struct query{int op,x,y,t;}q[1007];
void add(int& x,int y){x+=y;if (x>=MOD) x-=MOD;}
void solve(){
	memset(f,0,sizeof(f));memset(g,0,sizeof(g));
	f[0][m][0][0]=1;
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j){
		auto now=f[i][j],pre=(j==1?f[i-1][m]:f[i][j-1]);
		for (int s=0;s<(1<<m);++s) for (int t=0;t<2;++t) if (pre[s][t]){
			if (t&&((s>>j-1)&1)) continue;
			int tmp=pre[s][t];
			if (!a[i][j]){
				if (t||((s>>j-1)&1)) continue;
				add(now[s][t],tmp);
				continue;
			}
			if (t){
				if (j<m&&!((s>>j)&1)&&a[i][j+1]) add(now[s][t],tmp);
				add(now[s][0],tmp);
			}
			else if ((s>>j-1)&1){
				if (i<n&&a[i+1][j]) add(now[s][t],tmp);
				add(now[s^(1<<j-1)][t],tmp);
			}
			else{
				add(now[s][0],tmp);
				if (i<n&&a[i+1][j]) add(now[s|(1<<j-1)][0],tmp);
				if (j<m&&!((s>>j)&1)&&a[i][j+1]) add(now[s][1],tmp);
			}
		}
	}
	g[n+1][1][0][0]=1;
	for (int i=n;i;--i) for (int j=m;j;--j){
		auto now=g[i][j],pre=(j==m?g[i+1][1]:g[i][j+1]);
		for (int s=0;s<(1<<m);++s) for (int t=0;t<2;++t) if (pre[s][t]){
			if (t&&((s>>j-1)&1)) continue;
			int tmp=pre[s][t];
			if (!a[i][j]){
				if (t||((s>>j-1)&1)) continue;
				add(now[s][t],tmp);
				continue;
			}
			if (t){
				if (j&&!((s>>j-2)&1)&&a[i][j-1]) add(now[s][t],tmp);
				add(now[s][0],tmp);
			}
			else if ((s>>j-1)&1){
				if (i&&a[i-1][j]) add(now[s][t],tmp);
				add(now[s^(1<<j-1)][t],tmp);
			}
			else{
				add(now[s][0],tmp);
				if (i&&a[i-1][j]) add(now[s|(1<<j-1)][0],tmp);
				if (j&&!((s>>j-2)&1)&&a[i][j-1]) add(now[s][1],tmp);
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) cin>>a[i][j];
	cin>>T;
	for (int i=1;i<=T;++i){
		cin>>q[i].op;
		if (q[i].op==1) cin>>q[i].x>>q[i].y;
		if (q[i].op==2) cin>>q[i].x;
		if (q[i].op==3) cin>>q[i].x;
		if (q[i].op==4) cin>>q[i].x>>q[i].y>>q[i].t;
		if (q[i].op==5) cin>>q[i].y>>q[i].x>>q[i].t;
	}
	solve();
	cout<<f[n][m][0][0]<<endl;
	for (int i=1;i<=T;++i){
		if (q[i].op==1){
			int sum=0,x=q[i].x,y=q[i].y;
			auto F=(y==1?f[x-1][m]:f[x][y-1]),G=(y==m?g[x+1][1]:g[x][y+1]);
			int msk=((1<<m)-1)^(1<<y-1);
			sum=(ll)F[0][0]*G[0][0]%MOD;
			for (int s=msk;s;s=s-1&msk) sum=(sum+(ll)F[s][0]*G[s][0])%MOD;
			ans[i]=sum;
		}
		if (q[i].op==2) ans[i]=(ll)f[q[i].x-1][m][0][0]*g[q[i].x+1][1][0][0]%MOD;
		if (q[i].op==4){
			int sum=0,x=q[i].x,yL=q[i].y,yR=q[i].y+q[i].t;
			auto F=(yL==1?f[x-1][m]:f[x][yL-1]),G=(yR==m?g[x+1][1]:g[x][yR+1]);
			int msk=((1<<m)-1)^((1<<yR)-(1<<yL-1));
			sum=(ll)F[0][0]*G[0][0]%MOD;
			for (int s=msk;s;s=s-1&msk) sum=(sum+(ll)F[s][0]*G[s][0])%MOD;
			ans[i]=sum;
		}
	}
	for (int i=1;i<=max(n,m);++i) for (int j=1;j<i;++j) swap(a[i][j],a[j][i]);
	swap(n,m);solve();
	for (int i=1;i<=T;++i){
		if (q[i].op==3) ans[i]=(ll)f[q[i].x-1][m][0][0]*g[q[i].x+1][1][0][0]%MOD;
		if (q[i].op==5){
			int sum=0,x=q[i].x,yL=q[i].y,yR=q[i].y+q[i].t;
			auto F=(yL==1?f[x-1][m]:f[x][yL-1]),G=(yR==m?g[x+1][1]:g[x][yR+1]);
			int msk=((1<<m)-1)^((1<<yR)-(1<<yL-1));
			sum=(ll)F[0][0]*G[0][0]%MOD;
			for (int s=msk;s;s=s-1&msk) sum=(sum+(ll)F[s][0]*G[s][0])%MOD;
			ans[i]=sum;
		}
	}
	for (int i=1;i<=T;++i) cout<<ans[i]<<'\n';
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...