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

· · 题解

思路和 [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;
}