题解：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})。可以通过。

#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;
}