bzoj3235 好方的蛇

感谢某神犇的指教…

f[i][j]->右下角在[1,i],[1,j]范围内的subsnake
r[i][j]->右上角在[i,n],[1,j]范围内的subsnake
g[i][j]->左上角在[i,n],[j,n]范围内的subsnake
最后的res[i][j]->左下角是(i,j)范围内的subsnake

单调栈维护f,r,g,res,最后统计答案时容斥一下,重复计数的部分是一块完全在另一块的右上角的情况,减去即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000+5;
const int mo=10007;
char s[maxn][maxn];
int n,a[maxn][maxn],res[maxn][maxn];
int ss[maxn],h[maxn],tp,ret,f[maxn][maxn],r[maxn][maxn],g[maxn][maxn];
//f[i][j]->右下角在[1,i],[1,j]范围内的subsnake
//r[i][j]->右上角在[i,n],[1,j]范围内的subsnake
//g[i][j]->左上角在[i,n],[j,n]范围内的subsnake
//最后的res[i][j]->左下角是(i,j)范围内的subsnake
void push(int pos)
{
ret+=(pos-ss[tp])*h[pos];
if(!tp || h[ss[tp]]!=h[pos]) ++tp;
ss[tp]=pos;
}
void pop()
{
ret-=h[ss[tp]]*(ss[tp]-ss[tp-1]);
tp--;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=s[i][j]=='B'?1:0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) h[j]=a[i][j]==1?h[j]+1:0;
for(int j=1;j<=n;j++){
while(tp && h[j]<h[ss[tp]]) pop();
push(j);
res[i][j]=ret-(a[i][j]==1);
}
ret=tp=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=(f[i-1][j]+f[i][j-1]-f[i-1][j-1]+res[i][j])%mo;
}
}
memset(h,0,sizeof(int)*(n+1));
for(int i=n;i>=1;i--){
for(int j=1;j<=n;j++) h[j]=a[i][j]==1?h[j]+1:0;
for(int j=1;j<=n;j++){
while(tp && h[j]<h[ss[tp]]) pop();
push(j);
res[i][j]=ret-(a[i][j]==1);
}
ret=tp=0;
}
for(int i=n;i>=1;i--){
for(int j=1;j<=n;j++){
r[i][j]=(r[i+1][j]+r[i][j-1]-r[i+1][j-1]+res[i][j])%mo;
}
}
memset(h,0,sizeof(int)*(n+1));ss[0]=n+1;
//ss[0]=n+1是在压栈时减掉栈首时用到的,因为这里是倒着循环
for(int i=n;i>=1;i--){
for(int j=n;j>=1;j--) h[j]=a[i][j]==1?h[j]+1:0;
for(int j=n;j>=1;j--){
while(tp && h[j]<h[ss[tp]]) pop();
push(j);
res[i][j]=-ret-(a[i][j]==1);
}
ret=tp=0;
}
for(int i=n;i>=1;i--){
for(int j=n;j>=1;j--){
g[i][j]=(g[i+1][j]+g[i][j+1]-g[i+1][j+1]+res[i][j])%mo;
}
}
int ans=0;
for(int i=n;i>=1;i--){
for(int j=n;j>=1;j--){
ans=(ans+(1ll*res[i][j]*(f[i-1][n]+f[n][j-1]-f[i-1][j-1]))%mo)%mo;
}
}
memset(h,0,sizeof(int)*(n+1));
for(int i=1;i<=n;i++){
for(int j=n;j>=1;j--) h[j]=a[i][j]==1?h[j]+1:0;
for(int j=n;j>=1;j--){
while(tp && h[j]<h[ss[tp]]) pop();
push(j);
res[i][j]=-ret-(a[i][j]==1);
ans=(ans-(res[i][j]*r[i+1][j-1])%mo+mo)%mo;
}
ret=tp=0;
}
printf("%d\n",(ans+mo)%mo);
return 0;
}