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

思路

我们发现一共经过 $5$ 片荷叶等同于跳 $4$ 次。
而如果每次都不是原地跳的话，只有跳出一个矩形才会造成第 $5$ 片和第 $1$ 片是同一片。
但是我们很难限制在中途不形成矩形，否则会产生很多种状态，所以考虑正难则反。
首先忽略不形成矩形的条件。
那么可以很容易地得出一个状态：$f_{x,y,i,0/1}$ 表示现在在 $(x,y)$，一共跳了 $i$ 次，上次跳了 $0/1$ 的方向（分别代表同一列和同一行）。
转移也不是很难想，$f_{x,y,i,0}=\sum_{j=1}^{m}f_{x,j,i-1,1}-f_{x,y,i-1,1}$，同理可得 $f_{x,y,i,1}=\sum_{j=1}^{n}f_{j,y,i-1,0}-f_{x,y,i-1,0}$。
对式子进行分析，首先若此次的转移方向是同一列，则是要从所有同一列的少跳一步且上一次是同一行的状态转移而来，并且由于不能原地跳，所以还要再减掉由自己转移而来的状态。
但是这个时间复杂度无法接受，那么先提前对每一行和每一列的值做加和预处理，就可以做到 $O(nm)$ 做完整个 DP。
此时我们就得到了有可能在最后一跳返回起点的情况，考虑如何剔除掉非法情况。
发现只需要找出所有矩形，因为可以从每个顶点分别出发，又可以选择是顺时针还是逆时针，所以将矩形数量 $\times8$ 就是多余的状态。
矩形咋找呢，我们用 bitset 维护每一列的情况，将两列按位与起来，$1$ 的数量就是这两列存在相同 $y$ 值的个数。
时间复杂度 $O(\frac{n^2m}{w})$，由于 $n,m$ 均只有 $2000$，还是可以接受的。
此时已经拿到了 93pts，最后一个 subtask 会空间超限。
考虑滚动数组优化 DP，空间也可以通过。
然后状态数组，加和，统计答案会爆 long long，均要开 __int128，注意中间值的处理，都开 __int128。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=2047;
int n,m;
__int128 f[N][N][2],s[N][2],ans;
bitset<N>a[N];
signed main(){
	read(n,m);
	rep(x,1,n){
		rep(y,1,m){
			char c;cin>>c;
			a[x][y]=c-'0';
		}
	}
	rep(x,1,n){
		rep(y,1,m){
			if(a[x][y]==0)continue;
			f[x][y][0]=1;
			f[x][y][1]=1;
		}
	}
	rep(i,1,4){
		rep(x,1,n)s[x][0]=0;
		rep(y,1,m)s[y][1]=0;
		rep(x,1,n){
			rep(y,1,m){
				if(a[x][y]==0)continue;
				s[x][0]+=f[x][y][0];
				s[y][1]+=f[x][y][1];
			}
		}
		rep(x,1,n){
			rep(y,1,m){
				if(a[x][y]==0)continue;
				__int128 xy0=f[x][y][0],xy1=f[x][y][1];
				f[x][y][0]=s[y][1]-xy1;
				f[x][y][1]=s[x][0]-xy0;
			}
		}
	}
	rep(x,1,n){
		rep(y,1,m){
			ans+=f[x][y][0];
			ans+=f[x][y][1];
		}
	}
	rep(x1,1,n){
		rep(x2,x1+1,n){
			__int128 v=(a[x1]&a[x2]).count();
			ans-=(v*(v-1)*4);
		}
	}
	print(ans);
}