如果不考虑荷叶会掉，那么重复就只有矩形的可能。

答案就变成 dp - 矩形总数。

然后需要开 int128 和前缀和优化。

详见注释：

#include<bits/stdc++.h>
using namespace std;

const int N = 2010;

char s[N];
int a[N][N];
bitset<2001> b[N], bs; 
__int128 dpi[2][N][N];
__int128 dpj[2][N][N];
__int128 sumi[N];
__int128 sumj[N];

template<typename T> void qr(T &x) {
	char c = getchar(); int f = 1; x = 0;
	for (; !isdigit(c); c = getchar()) if (c == '-') {
		f = -1;
	}
	for (; isdigit(c); c = getchar()) {
		x = x * 10 + (c - '0');
	}
	x *= f;
}

template<typename T> void qw(T x) {
	if (x < 0) {
		putchar('-');
		x *= -1;
	}
	if (x > 9) {
		qw(x / 10);
	}
	putchar(x % 10 + '0');
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> (s + 1);
		for (int j = 1; j <= m; j ++) {
			a[i][j] = s[j] - '0';
			b[i][j] = a[i][j];
		}
	}
	
	memset(dpi, 0, sizeof(dpi));
	memset(dpj, 0, sizeof(dpj));
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			dpi[0][i][j] = dpj[0][i][j] = a[i][j];
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		sumi[i] = 0;
		for (int j = 1; j <= m; j ++) {
			sumi[i] += dpi[0][i][j];
		}
	}
	
	for (int j = 1; j <= m; j ++) {
		sumj[j] = 0;
		for (int i = 1; i <= n; i ++) {
			sumj[j] += dpj[0][i][j];
		}
	}
	
	for (int T = 1; T <= 4; T ++) {
		int opt = (T & 1);
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= m; j ++) if (a[i][j] == 1){
				dpi[opt][i][j] = dpj[opt][i][j] = 0;
				
				dpj[opt][i][j] = sumi[i] - dpi[opt ^ 1][i][j];
//				for (int k = 1; k <= m; k ++) if (a[i][k] == 1 && k != j){
//					dpj[opt][i][j] += dpi[opt ^ 1][i][k];
//				}
				
				dpi[opt][i][j] = sumj[j] - dpj[opt ^ 1][i][j];
//				for (int k = 1; k <= n; k ++) if (a[k][j] == 1 && k != i){
//					dpi[opt][i][j] += dpj[opt ^ 1][k][j];
//				}
			}
		}
		
		for (int i = 1; i <= n; i ++) {
			sumi[i] = 0;
			for (int j = 1; j <= m; j ++) {
				sumi[i] += dpi[opt][i][j];
			}
		}
		
		for (int j = 1; j <= m; j ++) {
			sumj[j] = 0;
			for (int i = 1; i <= n; i ++) {
				sumj[j] += dpj[opt][i][j];
			}
		}
	}
	
	__int128 ans = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) if (a[i][j]) { 
			ans += dpi[0][i][j] + dpj[0][i][j];
		}
	}
	
//	qw(ans);
//	putchar('\n');
	
	for (int i = 1; i <= n; i ++) {
		for (int j = i + 1; j <= n; j ++) {
			bs = b[i] & b[j];
			__int128 t = bs.count();
			ans -= t * (t - 1) * 4;
			// 有 t 个竖着的 1 点对，从里面选两个
			// 顺序是重要的，还可以选 4 个起始点 
		}
	}
	
	qw(ans);
	putchar('\n');
	
	return 0;
} 

思路和 [ICPC 2025 APC] Control Towers 非常相像的一道题。

先弱化一下不能重复经过同一片荷叶的限制，直接算跳 $5$ 步且相邻两个跳到的位置不同能形成的路径数量。设 $f_{r,x,y,0/1}$ 表示当前跳了 $r$ 步，位于 $(x,y)$，上一次跳动是从同一行 / 同一列的方案数。初始时 $f_{0,x,y,0}=f_{0,x,y,1}=1$，转移是简单的：不妨认为这一次从同一行跳过来，那么有 $f_{r,x,y,0}=\sum\limits_{j=1}^m f_{r-1,x,j,1}-f_{r-1,x,y,1}$，对于每一行预处理一下和就能快速转移；列同理。于是可以在 $O(nm)$ 的时间复杂度内计算出路径数量。

尝试思考什么时候会算重。发现只有一种情况，就是经过了四个形成矩形的位置，最后跳回了原位。问题变为了求出有多少对 $(x_1,y_1,x_2,y_2)(x_1<y_1\land x_2<y_2)$ 满足 $(x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2)$ 四个位置都有荷叶，将这个数量乘以 $8$（可以自由选择起点和顺逆时针），从答案中减掉即可。这个数量很好求，枚举 $x_1,x_2$，记 $c$ 为满足 $(x_1,y)$ 和 $(x_2,y)$ 均为荷叶的 $y$ 的数量，那么需要求的值即为 $\frac{c(c-1)}{2}$。$c$ 可以用 bitset 来求，这一部分的时间复杂度为 $O\left(\frac{n^2m}{w}\right)$。

综上，时间复杂度为 $O\left(nm+\frac{n^2m}{w}\right)$，常数不要写得太大。以及注意存储答案可能需要 __int128。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
typedef bitset<2000> B;
void write(ll x){
  if(x>9)write(x/10);
  cout<<(char)(x%10+48);
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,m; cin>>n>>m;
  vector<string> s(n);
  for(auto &i:s)cin>>i;
  vector f(n,vector<array<ll,2> >(m));
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      f[i][j][0]=f[i][j][1]=s[i][j]&1;
  for(int r=1;r<5;r++){
    vector<ll> rs(n),cs(m);
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        rs[i]+=f[i][j][0],cs[j]+=f[i][j][1];
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        if(s[i][j]&1){
          ll x=f[i][j][0],y=f[i][j][1];
          f[i][j][0]=cs[j]-y,f[i][j][1]=rs[i]-x;
        }
  } // DP 部分
  ll c=0;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      c+=f[i][j][0]+f[i][j][1];
  vector<B> b(n);
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      if(s[i][j]&1)b[i].set(j);
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++){
      int x=(b[i]&b[j]).count();
      c-=x*(x-1)*4;
    } // 扣掉算重的部分
  write(c),cout<<endl;
  return 0;
}

subtask 1,2

这道题由于青蛙走的步数很少，只有五步，所以很容易想到进行 dfs。

时间复杂度：$O((n\times m)^5)$

代码略。

subtask 2.5

设 $dp_{i,j,k,0/1}$ 表示在 $(i,j)$ 时，走了 $k$ 步，这一步是横着/竖着走的方案数。转移方程为：$dp_{i,j,k,0}=(\sum_{l=1}^{n} dp_{l,j,k-1,1})-dp_{i,j,k-1,1}$，$dp_{i,j,k,1}=(\sum_{l=1}^{m} dp_{i,l,k-1,0})-dp_{i,j,k-1,0}$。

当前时间复杂度是 $O(n^2\times m+m^2\times n)$ 的。

然后我们会发现答案会有不合法的情况：如果前面选的四个点分别为 $(x_1,y_1)$，$(x_1,y_2)$，$(x_2,y_2)$，$(x_2,y_1)$，那么根据我们的转移方程，第五个点就可能为 $(x_1,y_1)$，即不合法的情况为一个矩形，并且通过简单枚举，可以发现一个矩形内有八种方案。

现在的问题是：计算矩形数量。

我们可以直接暴力枚举一行 $i$ 与另一行 $j$，$O(m)$ 统计两行的同一列均为 1 的个数 $cnt$，那么最后答案就应该减少 $\frac{cnt\times (cnt-1)}{2} \times 8$。

code

const int N=2e3+5;
int n,m,dp[N][N][5][2],ans;
string s[N];
signed main(){
//	freopen("five.in","r",stdin);
//	freopen("five.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		read_str(s[i]);
		s[i]=" "+s[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='1'){
				dp[i][j][0][0]=dp[i][j][0][1]=1;
			}
		}
	} 
	for(int k=1;k<5;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[i][j]=='0')continue;
				for(int l=1;l<=n;l++){
					if(s[l][j]=='0'||l==i)continue;
					dp[i][j][k][0]+=dp[l][j][k-1][1];
				}
				for(int l=1;l<=m;l++){
					if(s[i][l]=='0'||l==j)continue;
					dp[i][j][k][1]+=dp[i][l][k-1][0];
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans+=dp[i][j][4][0]+dp[i][j][4][1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int cnt=0;
			for(int k=1;k<=m;k++){
				if(s[i][k]=='1'&&s[j][k]=='1'){
					cnt++;
				}
			} 
			ans-=cnt*(cnt-1)*4; 
		}
	}
	write(ans);
	flush_out();
}

总的时间复杂度为 $O(n^2\times m+m^2\times n+n^2\times m)$。

但是由于常数很大，所以过不了 subtask 3。

subtask 3

我们发现在转移方程中，有一个求和结构，并且这个求和要算 $O(n)$ 次（假设 $n$ 和 $m$ 同阶）。所以很容易想到提前在外面算好值，只算一次即可。时间复杂度就降到了 $O(n\times m)$。

code

const int N=2e3+5;
int n,m,dp[N][N][5][2],ans,sum0[N][5],sum1[N][5];
string s[N];
signed main(){
//	freopen("five.in","r",stdin);
//	freopen("five.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		read_str(s[i]);
		s[i]=" "+s[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='1'){
				dp[i][j][0][0]=dp[i][j][0][1]=1;
				sum1[j][0]+=dp[i][j][0][1];
				sum0[i][0]+=dp[i][j][0][0];
			}
		}
	} 
	for(int k=1;k<5;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[i][j]=='0')continue;
				dp[i][j][k][0]+=sum1[j][k-1]-dp[i][j][k-1][1];
				dp[i][j][k][1]+=sum0[i][k-1]-dp[i][j][k-1][0];
				sum1[j][k]+=dp[i][j][k][1];
				sum0[i][k]+=dp[i][j][k][0];
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans+=sum0[i][4];
	}
	for(int i=1;i<=m;i++){
		ans+=sum1[i][4];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int cnt=0;
			for(int k=1;k<=m;k++){
				if(s[i][k]=='1'&&s[j][k]=='1'){
					cnt++;
				}
			} 
			ans-=cnt*(cnt-1)*4; 
		}
	}
	write(ans);
	flush_out();
}

总的时间复杂度为 $O(n\times m+n^2\times m)$。

subtask 3.5

现在的时间复杂度瓶颈在于统计矩形。我们可以拿 bitset 记录下每一行的状态。枚举两行，将它们的状态相 &，统计为 1 的数量 $cnt$，最后答案就应该减少 $\frac{cnt\times (cnt-1)}{2} \times 8$。

这个的时间复杂度为 $O(\frac{n^2\times m}{\omega})$。

code

const int N=2e3+5;
int n,m,dp[N][N][5][2],ans,sum0[N][5],sum1[N][5];
string s[N];
bitset<N>bs[N],res;
signed main(){
//	freopen("five.in","r",stdin);
//	freopen("five.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		read_str(s[i]);
		s[i]=" "+s[i];
		for(int j=1;j<=m;j++){
			if(s[i][j]=='1')bs[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='1'){
				dp[i][j][0][0]=dp[i][j][0][1]=1;
				sum1[j][0]+=dp[i][j][0][1];
				sum0[i][0]+=dp[i][j][0][0];
			}
		}
	} 
	for(int k=1;k<5;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[i][j]=='0')continue;
				dp[i][j][k][0]+=sum1[j][k-1]-dp[i][j][k-1][1];
				dp[i][j][k][1]+=sum0[i][k-1]-dp[i][j][k-1][0];
				sum1[j][k]+=dp[i][j][k][1];
				sum0[i][k]+=dp[i][j][k][0];
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans+=sum0[i][4];
	}
	for(int i=1;i<=m;i++){
		ans+=sum1[i][4];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			res=bs[i]&bs[j];
			int cnt=res.count();
			ans-=cnt*(cnt-1)*4; 
		}
	}
	write(ans);
	flush_out();
}

注意到当所有的 $s_{i,j}$ 全为 1 时，答案已经爆 long long 了，所以需要开 __int128。

现在总的时间复杂度为 $O(n\times m+\frac{n^2\times m}{\omega})$。

但是这份代码 MLE 了！我们来看下一步优化。

subtask 4

观察转移方程：$dp_{i,j,k,0}+=sum1_{j,k-1}-dp_{i,j,k-1,1}$，$dp_{i,j,k,1}+=sum0_{i,k-1}-dp_{i,j,k-1,0}$。发现第三维只可能为 $k$ 或 $k-1$。那么用滚动优化即可，有效地降低了空间复杂度。

code

const int N=2e3+5;
int n,m,dp[N][N][2][2],ans,sum0[N][5],sum1[N][5];
string s[N];
bitset<N>bs[N],res;
signed main(){
//	freopen("five.in","r",stdin);
//	freopen("five.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		read_str(s[i]);
		s[i]=" "+s[i];
		for(int j=1;j<=m;j++){
			if(s[i][j]=='1')bs[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='1'){
				dp[i][j][0][0]=dp[i][j][0][1]=1;
				sum1[j][0]+=dp[i][j][0][1];
				sum0[i][0]+=dp[i][j][0][0];
			}
		}
	} 
	for(int k=1;k<5;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[i][j]=='0')continue;
				dp[i][j][1][0]+=sum1[j][k-1]-dp[i][j][0][1];
				dp[i][j][1][1]+=sum0[i][k-1]-dp[i][j][0][0];
				sum1[j][k]+=dp[i][j][1][1];
				sum0[i][k]+=dp[i][j][1][0];
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				dp[i][j][0][1]=dp[i][j][1][1];
				dp[i][j][0][0]=dp[i][j][1][0];
				dp[i][j][1][1]=dp[i][j][1][0]=0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans+=sum0[i][4];
	}
	for(int i=1;i<=m;i++){
		ans+=sum1[i][4];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			res=bs[i]&bs[j];
			int cnt=res.count();
			ans-=cnt*(cnt-1)*4; 
		}
	}
	write(ans);
	flush_out();
} 

那么就可以轻松通过了。