SAKIKO

KazamaRuri · 2025-11-27 13:01:43 · 题解

傻瓜做法矩阵分治，时间 O(nm\log(nm)) 略差。

枚举起始行和结束行，然后找到极小无洞的列区间。

问题变成统计强制过定点，长度有下界的区间数。

trival 的讨论一下就好。

被打回了，解法需要多体现。我感觉上面写得很清楚了，就是分治完跑暴力。

具体一点，对行分治时，对每一列从中间行开始找到最上和最下的洞，行的取值范围可以确定。

枚举起始列和结束列 l,r，并且把取值范围取并。

然后限制只剩下跨过 mid 和长度 \ge \lceil \frac{k}{r-l+1} \rceil，求满足条件的子区间数。

对这个计数明显是普及难度，再不会就没话说了。

还是把代码加上了。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define lb(x) (x&-x)
#define fi first
#define se second
#define all(v) v.begin(),v.end() 
using ull=unsigned long long;
using pii=pair<int,int>;
const int mod=998244353;
void chkmin(int &x,int y){ if(x>y) x=y; }
void chkmax(int &x,int y){ if(x<y) x=y; }
ll qp(ll x,int y){ ll res=1; for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod; return res; }
const int N=2005;
int n,m,k,a[N][N],L[N],R[N]; ll res;
inline int S(int l,int r,int k){ return l>r?0:(k-1)*(r-l+1)+(l+r)*(r-l+1)/2; }
inline int calc(int l,int mid,int r,int k){
    return r-l+1<k?0:(min(r-k+1,mid)-l+1)*(r+1)-S(max(mid+2-k,l),min(r-k+1,mid),k)-max(0,mid-k+2-l)*(mid+1);
}
void solve(int x1,int y1,int x2,int y2){
    if(x1==x2&&y1==y2) return ;
    if(x2-x1>y2-y1){
        int mid=x1+x2>>1; solve(x1,y1,mid,y2),solve(mid+1,y1,x2,y2);
        for(int i=y1;i<=y2;i++){
            L[i]=mid,R[i]=mid+1;
            while(L[i]>=x1&&!a[L[i]][i]) --L[i];
            while(R[i]<=x2&&!a[R[i]][i]) ++R[i];
        }
        for(int i=y1;i<=y2;i++){
            int l=x1-1,r=x2+1;
            for(int j=i;j<=y2;j++){
                l=max(l,L[j]),r=min(r,R[j]);
                if(l==mid||r==mid+1) break;
                res+=calc(l+1,mid,r-1,(k+j-i)/(j-i+1));
            }
        }
    }else{
        int mid=y1+y2>>1; solve(x1,y1,x2,mid),solve(x1,mid+1,x2,y2);
        for(int i=x1;i<=x2;i++){
            L[i]=mid,R[i]=mid+1;
            while(L[i]>=y1&&!a[i][L[i]]) --L[i];
            while(R[i]<=y2&&!a[i][R[i]]) ++R[i];
        }
        for(int i=x1;i<=x2;i++){
            int l=y1-1,r=y2+1;
            for(int j=i;j<=x2;j++){
                l=max(l,L[j]),r=min(r,R[j]);
                if(l==mid||r==mid+1) break;
                res+=calc(l+1,mid,r-1,(k+j-i)/(j-i+1));

            }
        }
    }
}
void HitachiMako(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",a[i]+j);
            if(k==1) res+=!a[i][j];
        }
    for(int i=0;i<=n+1;i++) a[i][0]=a[i][m+1]=1;
    for(int i=0;i<=m+1;i++) a[0][i]=a[n+1][i]=1;
    solve(1,1,n,m);
    printf("%lld",res);
}
int main(){
    int T=1;
    while(T--) HitachiMako();
    return 0;
}