[CF273D] Dima and Figure 题解

容易发现，一个方案要合法，其每一行的黑格子必须形成一个区间。证明是取同一行任意两个点

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)

。

code

CPP

#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;
}

[CF273D] Dima and Figure 题解

文章操作

相关推荐

评论

[CF273D] Dima and Figure 题解