[CF273D] Dima and Figure 题解

aeiouaoeiu · 2025-11-23 11:26:15 · 题解

容易发现，一个方案要合法，其每一行的黑格子必须形成一个区间。证明是取同一行任意两个点 a,b，则 a\to b 步数必须为 |a-b|，这要求 [a,b] 均被涂黑。

再进一步观察，发现若从上往下看每一行，区间的左端点必然是先减后增，具体证明是，若有先增后减，各取增段和减段任意一行的左端点，这两个点只能靠着连通块的边界走，而这必然大于其曼哈顿距离。同理可以得到右端点先增后减。

于是可以直接把这些属性全部压进状态。设 f_{i,0/1,0/1,l,r} 表示当前考虑到第 i 行，左端点到了减/增段，右端点到了增/减段，这一行左右端点分别为 l,r 的方案数。若转移 (i,a,b,l,r)\to(j,c,d,l',r')，l',r' 需要满足如下条件。

• 整个黑色区域形成连通块，即 [l,r] 与 [l',r'] 有交。
• 根据 c，确定 l 与 l' 的大小关系，d 同理。
• 为了去重（避免 l 相等时状态反复横跳），钦定 a=c 时才能使得 l=l'，b=d 同理。

注意处理由空区间的转移，即这一行为连通块第一行的情况。

注意到对 l',r' 的限制分别形成两个区间，于是可以视作二维平面上的矩形加，使用二维差分优化即可。

时间复杂度为大常数 \mathcal{O}(nm^2)。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=307,ee=1e18,p=1e9+7;
ll n,m,a[maxn][maxn],f[2][2][2][maxn][maxn],ans;
void ups(ll &a,ll b){a=(a+b>=p)?(a+b-p):(a+b);}
void mul(ll &a,ll b){a=(a<b)?(a+p-b):(a-b);}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(ll t=0,i0,i1,x1,y1,v,x2,y2;t<=n;t++){
        i0=t&1,i1=i0^1;
        memset(f[i1],0,sizeof(f[i1]));
        for(ll a=0;a<=1;a++)for(ll b=0;b<=1;b++){
            for(ll i=1;i<=m;i++)for(ll j=1;j<=m;j++){
                ups(f[i0][a][b][i][j],f[i0][a][b][i][j-1]);
            }
            for(ll i=1;i<=m;i++)for(ll j=1;j<=m;j++){
                ups(f[i0][a][b][i][j],f[i0][a][b][i-1][j]);
                if(i<=j) ups(ans,f[i0][a][b][i][j]);
            }
            for(ll i=1;i<=m;i++)for(ll j=1;j<i;j++) f[i0][a][b][i][j]=0;
            ups(f[i0][a][b][m][1],1);
            if(t==n) continue;
            for(ll c=a;c<=1;c++)for(ll d=b;d<=1;d++){
                for(ll l=1;l<=m;l++)for(ll r=1;r<=m;r++){
                    v=f[i0][a][b][l][r];
                    if(!v) continue;
                    if(l==m&&r==1&&(c!=0||d!=0)) continue;
                    x2=1,y2=m,x1=m,y1=1;
                    if(!(l==m&&r==1)){
                        x1=min(x1,r),y1=max(y1,l);
                        if(!c) x1=min(x1,l-(c!=a));
                        else x2=l+(c!=a);
                        if(!d) y1=max(y1,r+(b!=d));
                        else y2=r-(b!=d);
                    }
                    if(x2>x1||y1>y2) continue;
                    ups(f[i1][c][d][x2][y1],v);
                    mul(f[i1][c][d][x1+1][y1],v);
                    mul(f[i1][c][d][x2][y2+1],v);
                    ups(f[i1][c][d][x1+1][y2+1],v);
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

::::