题目链接

题解

求出每个点为顶点，分别求出左上，左下，右上，右下的矩形的个数\(g[i][j]\)

并预处理出\(f[i][j]\)表示点\((i,j)\)到四个角的矩形内合法矩形个数

就可以容斥计数啦

枚举顶点\((i,j)\)，乘上另一侧矩形个数，如图：

但是会算重，对于这样的情况

减去即可

求\(g[i][j]\)数组，枚举每一行，使用单调栈即可

复杂度\(O(n^2)\)

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<cmath>

#include<map>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define cls(s,v) memset(s,v,sizeof(s))

#define mp(a,b) make_pair<int,int>(a,b)

#define cp pair<int,int>

using namespace std;

const int maxn = 1005,maxm = 100005,INF = 0x3f3f3f3f,P = 10007;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}

	return flag ? out : -out;

}

int f[maxn][maxn][4],g[maxn][maxn][4],n;

int S[maxn][maxn],d[maxn][maxn][2];

int len[maxn],h[maxn],top,tot;

void Pre(){

	for (int j = 1; j <= n; j++){

		for (int i = 1; i <= n; i++){

			if (!S[i][j]) continue;

			d[i][j][0] = d[i - 1][j][0] + 1;

		}

	}

	for (int j = 1; j <= n; j++){

		for (int i = n; i; i--){

			if (!S[i][j]) continue;

			d[i][j][1] = d[i + 1][j][1] + 1;

		}

	}

	for (int k = 0; k <= 1; k++){

		for (int i = 1; i <= n; i++){

			top = 0; tot = 0;

			for (int j = 1; j <= n; j++){

				if (!S[i][j]){

					top = 0; tot = 0;

					continue;

				}

				int hh = d[i][j][k],L = 1;

				while (top && h[top] >= hh)

					tot = ((tot - h[top] * len[top] % P) + P) % P,L += len[top--];

				h[++top] = hh; len[top] = L; tot = (tot + hh * L) % P;

				g[i][j][k] = (tot - 1) % P;

			}

		}

	}

	for (int k = 0; k <= 1; k++){

		for (int i = 1; i <= n; i++){

			top = 0; tot = 0;

			for (int j = n; j; j--){

				if (!S[i][j]){

					top = 0; tot = 0;

					continue;

				}

				int hh = d[i][j][k],L = 1;

				while (top && h[top] >= hh)

					tot = ((tot - h[top] * len[top] % P) + P) % P,L += len[top--];

				h[++top] = hh; len[top] = L; tot = (tot + hh * L) % P;

				g[i][j][k + 2] = (tot - 1) % P;

			}

		}

	}

	for (int i = 1; i <= n; i++)

		for (int j = 1; j <= n; j++)

			f[i][j][0] = (f[i - 1][j][0] + f[i][j - 1][0] - f[i - 1][j - 1][0] + g[i][j][0]) % P;

	for (int i = n; i; i--)

		for (int j = 1; j <= n; j++)

			f[i][j][1] = (f[i + 1][j][1] + f[i][j - 1][1] - f[i + 1][j - 1][1] + g[i][j][1]) % P;

	for (int i = 1; i <= n; i++)

		for (int j = n; j; j--)

			f[i][j][2] = (f[i - 1][j][2] + f[i][j + 1][2] - f[i - 1][j + 1][2] + g[i][j][2]) % P;

	for (int i = n; i; i--)

		for (int j = n; j; j--)

			f[i][j][3] = (f[i + 1][j][3] + f[i][j + 1][3] - f[i + 1][j + 1][3] + g[i][j][3]) % P;

}

void work(){

	int ans = 0;

	for (int i = 1; i <= n; i++)

		for (int j = 1; j <= n; j++)

			ans = (ans + (f[1][j + 1][3] + f[i + 1][1][3] - f[i + 1][j + 1][3]) * g[i][j][0] % P) % P;

	for (int i = 1; i <= n; i++)

		for (int j = 1; j <= n; j++)

			ans = (ans + P - g[i][j][1] * f[i - 1][j + 1][2] % P) % P;

	printf("%d\n",(ans + P) % P);

}

int main(){

	n = read();

	REP(i,n){

		char c = getchar(); while (c != 'B' && c != 'W') c = getchar();

		REP(j,n) {S[i][j] = c == 'B' ? 1 : 0; c = getchar();}

	}

	Pre();

	work();

	return 0;

}

巴特西

BZOJ3235 [Ahoi2013]好方的蛇【单调栈 + dp】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ3235 [Ahoi2013]好方的蛇 【单调栈 + dp】

题目链接

题解

最新文章

热门文章

BZOJ3235 [Ahoi2013]好方的蛇【单调栈 + dp】