题解：P15567 [COCI 2025/2026 #5] 五步 / Pet

我们观察一下题目，题目说需要经过 5 个点，而且要转向。而一个矩形，最后就是 5 个点，而且没有第二种会经过重复点的情况了。此时，答案变成只满足经过了 5 个点并且每次转向的贡献减去形成一个矩形的贡献。

对于前者，使用动态规划，定义

f_{0/1,k,i,j}

分别表示这一步横着走或竖着走，当前经过

k+1

个点，处于

(i,j)

这个点。

我们对

f_{0,k,i,j}

进行讨论：（

f_{1,k,i,j}

同理）

当前横着走，就要把同一行的，并且上一步是竖着的转移过来，并且不能还在

(i,j)

：

f_{0,k,i,j} = (\sum_{X=1}^{m}f_{1,k-1,i,X}) - f_{1,k-1,i,j}

左边的求和可以用前缀和优化，优化到

O(n^2)

。（假设

n

和

m

同阶）。

对于一个矩形的情况，怎么求？考虑枚举矩形四个点所在的行数

x,y

。而一个合法的矩形，还要确定所在的列数。一个合法的列

p

要满足

(x,p)

和

(y,p)

都是

1

。而一个矩形可以通过两个合法的列组合而成，所以我们统计合法列的数量。而一个矩形，可以分成从四个顶点开始，每个顶点顺时针或逆时针共八种走法。

至此，我们在

O(n^3)

的时间内解决了问题，使用 bitset 优化这一求与的过程，就变成

O(\frac{n^3}{\omega})

。可以通过。

CPP

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2e3+10;
long long f[2][5][N][N],a[N][N];
bitset<N>c[N];
int n,m;
__int128 sum[2][N];

void print(__int128 x) {
	if (x>=10) {
		print(x / 10);
	}
	int o = x % 10;
	cout << o;
}
int main() {
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			char ch; cin>>ch;
			c[i][j] = f[1][0][i][j] = f[0][0][i][j] = a[i][j] = ch - '0';
		}
	}
	
	for (int k=1;k<=5;k++) {
		memset(sum,0,sizeof sum);
		for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++) {
			sum[0][i] += f[0][k-1][i][j];
		}
		for (int j=1;j<=m;j++) {
			for (int i=1;i<=n;i++) {
				sum[1][j] += f[1][k-1][i][j];
			}
		}
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				if (a[i][j] == 0) continue; 
//				for (int o=1;o<=n;o++) {
//					if (o != i && a[o][j] != 0) f[0][k][i][j] += f[1][k-1][o][j];
				f[1][k][i][j] = sum[0][i] - f[0][k-1][i][j];
//				}
//				for (int o=1;o<=m;o++) {
//					if (o != j && a[i][o] != 0) f[1][k][i][j] += f[0][k-1][i][o];
				f[0][k][i][j] = sum[1][j] - f[1][k-1][i][j];
//				}
			}
			
		}
	}
	__int128 ans = 0;
	
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			__int128 k = f[0][4][i][j] + f[1][4][i][j];
			ans += k;
		}
	}
	
	for (int i=1;i<=n;i++) {
		for (int j=i+1;j<=n;j++) {
			__int128 t = (c[i] & c[j]).count();
			ans -= t * (t-1) * 4;
		}
	}
	print(ans);
	return 0;
}

题解：P15567 [COCI 2025/2026 #5] 五步 / Pet

文章操作

相关推荐

评论

题解：P15567 [COCI 2025/2026 #5] 五步 / Pet