内网 2085马农

ACM

##Description
在观看完战马检阅之后,来自大草原的两兄弟决心成为超级“马农”,专门饲养战马。

兄弟两回到草原,将可以养马的区域,分为N*N的单位面积的正方形,并实地进行考察,归纳出了每个单位面积可以养马所获得的收益。接下来就要开始规划他们各自的马场了。

首先,两人的马场都必须是矩形区域。同时,为了方便两人互相照应,也为了防止马匹互相走散,规定两个马场的矩形区域相邻,且只有一个交点。最后,互不认输的两人希望两个马场的收益相当,这样才不会影响他们兄弟的感情。

现在,兄弟两找到你这位设计师,希望你给他们设计马场,问共有多少种设计方案。

##Input

第一行一个整数N,表示整个草原的大小为N*N。

接下来N行,每行N个整数A(i,j),表示第i行第j列的单位草地的收成。(注意:收益可能是负数,养马也不是包赚的,马匹也可能出现生病死亡等意外。)

1<=N<=50
-1000<A(i,j)<1000

##Output

输出符合两人要求的草原分配方案数。

##Sample Input

3 1 2 3 4 5 6 7 8 9

##Sample Output

2

##Hint

##Source

2014宁波初中 T2



宁波镇海中学的罗方炜给我们组的一场比赛。

此题主要靠技巧。枚举中心点,然后用数组hash。注意数组清空复杂度很大,每次清空必定超时。应该用一个栈来记录更改的地方,直接赋0.

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
94
95
#include&lt;map&gt;
#include&lt;set&gt;
#include&lt;cmath&gt;
#include&lt;stack&gt;
#include&lt;queue&gt;
#include&lt;string&gt;
#include&lt;cstdio&gt;
#include&lt;vector&gt;
#include&lt;cctype&gt;
#include&lt;cassert&gt;
#include&lt;utility&gt;
#include&lt;numeric&gt;
#include&lt;cstring&gt;
#include&lt;iostream&gt;
#include&lt;algorithm&gt;
using namespace std;
#define pr pair
#define PR pair&lt;int,int&gt;
#define MP make_pair
#define SI(x) set&lt;x&gt;::iterator
#define VI(x) vector&lt;x&gt;::iterator
#define MI(x,y) map&lt;x,y&gt;::iterator
#define SRI(x) set&lt;x&gt;::reverse_iterator
#define VRI(x) vector&lt;x&gt;::reverse_iterator
#define MRI(x,y) map&lt;x,y&gt;::reverse_iterator
#define F first
#define S second
#define Sz(x) (int)x.size()
#define clrQ(x) while(!x.empty)x.pop();
#define clr(x,y) memset(x,y,sizeof(x));
#if defined (_WIN32) || defined (__WIN32) || defined (WIN32) || defined (__WIN32__)
#define LL __int64
#define LLS "%" "I" "6" "4" "d"
#define LLU "%" "I" "6" "4" "u"
#define LL_MAX _I64_MAX
#else
#define LL long long
#define LLS "%" "l" "l" "d"
#define LLU "%" "l" "l" "u"
#define LL_MAX _I64_MAX
#endif
const int inf = ~0u &gt;&gt; 1;
const LL lnf = ~0ull &gt;&gt; 1;
/*start*/
#define N 55
#define M 2500000
int f[N][N],a[N][N];
int h[M&lt;&lt;1|1];
int st[N*N],top;
int n,m;
int main(int argc, char **argv) {
    while(~scanf("%d",&amp;n)){
        for (int i = 1; i &lt;= n; ++i) {
            for (int j = 1; j &lt;= n; ++j) {
                scanf("%d",&amp;a[i][j]);
                f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
            }
        }
        int res=top=0;
        for (int x = 1; x &lt;= n; ++x) {
            for (int y = 1; y &lt;= n; ++y) {
                for (int i = 1; i &lt;= x; ++i) {
                    for (int j = 1; j &lt;= y; ++j) {
                        st[top++]=f[x][y]-f[x][j-1]-f[i-1][y]+f[i-1][j-1]+M;
                        h[st[top-1]]++;
                    }
                }
                for (int i = x+1; i &lt;= n; ++i) {
                    for (int j = y+1; j &lt;= n; ++j) {
                        res+=h[f[i][j]-f[i][y]-f[x][j]+f[x][y]+M];
                    }
                }
                while(top){
                    h[st[--top]]=0;
                }
                for (int i = x; i &lt;= n; ++i) {
                    for (int j = 1; j &lt;= y; ++j) {
                        st[top++]=f[i][y]-f[x-1][y]-f[i][j-1]+f[x-1][j-1]+M;
                        h[st[top-1]]++;
                    }
                }
                for (int i = 1; i &lt; x; ++i) {
                    for (int j = y+1; j &lt;= n; ++j) {
                        res+=h[f[x-1][j]-f[x-1][y]-f[i-1][j]+f[i-1][y]+M];
                    }
                }
                while(top){
                    h[st[--top]]=0;
                }
            }
        }
        printf("%d\n",res);
    }
}