3235: [Ahoi2013]好方的蛇

链接

分析：

　　可以求出以每个点为顶点的满足条件的矩形有多少个，单调栈求。设为sum。

　　然后对这个数组进行二维前缀和，可以求出每个矩阵内，以右下角、左下角为端点的矩形有多少个，分别设为f，g。

　　然后可以枚举一个点（x,y），计算有多少个矩形的左上角是这个点，然后分别计算x上面的矩形，和y左面的矩形，与它不相交。此时一个每个矩形都和它左上角右上角的矩形计算了两次，减去即可。

　　调来调去，最后发现模数多写了个0。。。

代码:

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int mod = , N = ;

int a[N][N], f[N][N], g[N][N], u[N];

struct Node{ int x, sum, len; } sk[N];

char s[N];

int main() {

    int n = read();

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

        scanf("%s", s + );

        for (int j = ; j <= n; ++j) a[i][j] = s[j] == 'B';

    }

    int top = , sum = , ans = ;

    memset(u, , sizeof(u));

    for (int k, i = ; i <= n; ++i) {

        for (int j = ; j <= n; ++j) u[j] = a[i][j] ? u[j] +  : ;

        top = sum = ;

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

            k = ;

            while (top && sk[top].x > u[j]) k += sk[top].len, sum -= sk[top--].sum;

            sk[++top] = (Node){u[j], u[j] * k, k};

            sum += sk[top].sum - a[i][j];

            f[i][j] = f[i - ][j] + f[i][j - ] - f[i - ][j - ] + sum; f[i][j] %= mod;

            sum += a[i][j];

        }

    }

    memset(u, , sizeof(u));

    for (int k, i = ; i <= n; ++i) {

        for (int j = ; j <= n; ++j) u[j] = a[i][j] ? u[j] +  : ;

        top = sum = ;

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

            k = ;

            while (top && sk[top].x > u[j]) k += sk[top].len, sum -= sk[top--].sum;

            sk[++top] = (Node){u[j], u[j] * k, k};

            sum += sk[top].sum - a[i][j];

            g[i][j] = g[i - ][j] + g[i][j + ] - g[i - ][j + ] + sum; g[i][j] %= mod;

            sum += a[i][j];

        }

    }

    memset(u, , sizeof(u));

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

        for (int j = ; j <= n; ++j) u[j] = a[i][j] ? u[j] +  : ;

        top = sum = ;

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

            k = ;

            while (top && sk[top].x > u[j]) k += sk[top].len, sum -= sk[top--].sum;

            sk[++top] = (Node){u[j], u[j] * k, k};

            sum += sk[top].sum - a[i][j];

            ans += sum * f[n][j - ] + sum * f[i - ][n] - sum * f[i - ][j - ]; ans %= mod;

            sum += a[i][j];

        }

    }

    memset(u, , sizeof(u));

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

        for (int j = ; j <= n; ++j) u[j] = a[i][j] ? u[j] +  : ;

        top = sum = ;

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

            k = ;

            while (top && sk[top].x > u[j]) k += sk[top].len, sum -= sk[top--].sum;

            sk[++top] = (Node){u[j], u[j] * k, k};

            sum += sk[top].sum - a[i][j];

            ans = (ans - sum * g[i - ][j + ] % mod + mod) % mod;

            sum += a[i][j];

        }

    }

    cout << (ans + mod) % mod;

    return ;

}