P15567 [COCI 2025/2026 #5] 五步 / Pet Solution

Ptll · 2026-04-01 20:36:34 · 题解

链接

题解

转移是简单的，我们考虑记录 f_{i,j,k,0/1} 表示走 k 步走到 (i,j) 且最后一步是横/竖着走的方案数。

转移是显然的：

用前缀和优化即可。

我们发现，在只走 5 步的情况下，只有可能最后一步和第一步重合，只会形成一个长方形。

于是开始考虑枚举长方形的左上角与右下角进行容斥，这样就获得了 0pts 的好成绩。

事实上，我们可以考虑设第 i 行与第 j 行有 k 个都有荷叶的位置（i < j），用答案减去 k \times (k-1) \times 4 即可，这样你可以获得 93pts。

我们考虑用 bitset 优化这一过程，这样复杂度就是 O(nm + \frac {n^2 m} {w})。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <bitset>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (i128 x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=2e3+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,m,f[N][N][6][2],sum[2][N];
bitset<N> vis[N];
string s;
inline void solve () {
    n=read(),m=read();
    for (ll i=1;i<=n;i++) {
        cin>>s;
        for (ll j=1;j<=m;j++) {
            vis[i][j]=s[j-1]-'0';
            if (vis[i][j]) {
                f[i][j][1][1]=f[i][j][1][0]=1;
                sum[0][i]++;
                sum[1][j]++;
            }
        }
    }
    i128 ans=0;
    for (ll k=2;k<=5;k++) {
        for (ll i=1;i<=n;i++) {
            for (ll j=1;j<=m;j++) {
                if (!vis[i][j]) {
                    continue;
                }
                f[i][j][k][0]=sum[1][j]-f[i][j][k-1][1];
                f[i][j][k][1]=sum[0][i]-f[i][j][k-1][0];
            }
        }
        for (ll i=1;i<=n;i++) {
            sum[0][i]=0;
        }
        for (ll i=1;i<=m;i++) {
            sum[1][i]=0;
        }
        for (ll i=1;i<=n;i++) {
            for (ll j=1;j<=m;j++) {
                if (!vis[i][j]) {
                    continue;
                }
                sum[0][i]+=f[i][j][k][0];
                sum[1][j]+=f[i][j][k][1];
            }
        }
    }
    for (ll i=1;i<=n;i++) {
        ans+=sum[0][i];
    }
    for (ll i=1;i<=m;i++) {
        ans+=sum[1][i];
    }
    for (ll i=1;i<=n;i++) {
        for (ll j=i+1;j<=n;j++) {
            ll num=(vis[i]&vis[j]).count();
            ans-=(num-1)*num<<2;
        }
    }
    print(ans);
}
int main () {
    // freopen("five.in","r",stdin);
    // freopen("five.out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}