CSU 1813 蓋房子

Description

Bobo 在 ICPCCamp 買了一塊 n×m 的土地，其中有些格子是障礙。

他想選擇兩個矩形區域，建造兩座房子。 很明顯，用于蓋房子的區域不能包含障礙。同時，兩個區域不能相交（但是可以相鄰）。

9+7) 的餘數。

Input

輸入包含不超過 10 組資料。

3).

i。s

i

Output

Sample Input

2 2
00
01
3 4
1000
0001
0100      

Sample Output

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,int>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;
char s[N];
int n, m;
int c[N][N], a[N][N];
LL ls[N][N], lx[N][N], rs[N][N], rx[N][N];

void GetFour()
{
  memset(c, 0, sizeof(c));
  rep(i, 1, n)
  {
    rep(j, 1, m)
    {
      if (a[i][j] || c[i][j]) continue;
      while (c[i][j] <= n - i && !a[i + c[i][j]][j]) c[i][j]++;
      rep(k, 2, c[i][j]) c[i + k - 1][j] = c[i][j] - k + 1;
    }
    int sum = 0;  stack<pii> p;
    per(j, m, 1)
    {
      pii now = mp(c[i][j], 1);
      while (!p.empty() && p.top().ff > now.ff)
      {
        pii q = p.top();  sum -= q.ff * q.ss;
        now.ss += q.ss;   p.pop();
      }
      sum += now.ff * now.ss;
      p.push(now);
      ls[i][j] = sum;
    }
    sum = 0; while (!p.empty()) p.pop();
    rep(j, 1, m)
    {
      pii now = mp(c[i][j], 1);
      while (!p.empty() && p.top().ff > now.ff)
      {
        pii q = p.top();  sum -= q.ff * q.ss;
        now.ss += q.ss;   p.pop();
      }
      sum += now.ff * now.ss;
      p.push(now);
      rs[i][j] = sum;
    }
  }
  memset(c, 0, sizeof(c));
  per(i, n, 1)
  {
    rep(j, 1, m)
    {
      if (a[i][j] || c[i][j]) continue;
      while (c[i][j] < i && !a[i - c[i][j]][j]) c[i][j]++;
      rep(k, 2, c[i][j]) c[i - k + 1][j] = c[i][j] - k + 1;
    }
    int sum = 0;  stack<pii> p;
    per(j, m, 1)
    {
      pii now = mp(c[i][j], 1);
      while (!p.empty() && p.top().ff > now.ff)
      {
        pii q = p.top();  sum -= q.ff * q.ss;
        now.ss += q.ss;   p.pop();
      }
      sum += now.ff * now.ss;
      p.push(now);
      lx[i][j] = sum;
    }
    sum = 0; while (!p.empty()) p.pop();
    rep(j, 1, m)
    {
      pii now = mp(c[i][j], 1);
      while (!p.empty() && p.top().ff > now.ff)
      {
        pii q = p.top();  sum -= q.ff * q.ss;
        now.ss += q.ss;   p.pop();
      }
      sum += now.ff * now.ss;
      p.push(now);
      rx[i][j] = sum;
    }
  }
}

int main()
{
  while (scanf("%d%d", &n, &m) != EOF)
  {
    rep(i, 0, n + 1) rep(j, 0, m + 1) ls[i][j] = rs[i][j] = 0;
    rep(i, 1, n)
    {
      scanf("%s", s + 1);
      rep(j, 1, m) a[i][j] = s[j] - '0';
    }
    GetFour();
    LL L = 0, R = 0, ans = 0;
    rep(i, 1, n)
    {
      rep(j, 1, m) (R += ls[i][j]) %= mod;
      (ans += L * R) %= mod;        R = 0;
      rep(j, 1, m) (L += rx[i][j]) %= mod;
    }
    L = R = 0;
    rep(j, 1, m) 
    {
      rep(i, 1, n) (R += ls[i][j]) %= mod;
      (ans += L * R) %= mod;        R = 0;
      rep(i, 1, n) (L += rx[i][j]) %= mod;
    }
    rep(i, 1, n)
    {
      rep(j, 1, m)
      {
        rx[i][j] += rx[i - 1][j] + rx[i][j - 1] - rx[i - 1][j - 1];
        (ans -= rx[i][j] * ls[i + 1][j + 1]) %= mod;
      }
      per(j, m, 1)
      {
        lx[i][j] += lx[i - 1][j] + lx[i][j + 1] - lx[i - 1][j + 1];
        (ans -= lx[i][j] * rs[i + 1][j - 1]) %= mod;
      }
    }
    printf("%lld\n", (ans + mod) % mod);
  }
  return 0;
}