HDU 6052 – To my boyfriend | 2017 Multi-University Training Contest 2

说实话不是很懂按题解怎么写，思路来源于 http://blog.csdn.net/calabash_boy/article/details/76272704?yyue=a21bo.50862.201879

写起来倒是挺短的。

/*
HDU 6052 - To my boyfriend [ 分析,期望 ]  |  2017 Multi-University Training Contest 2
题意：
给出一个N*M的数字矩阵
求子矩阵的不同数字的个数的期望
限制 N,M <= 100
分析：
统计单点对答案的贡献
先定一个统计标准，比如：某种颜色对于某个矩阵的贡献由该矩阵中最右上方（先上后右）的该颜色的点所贡献
则单点对答案的贡献则为它所在的矩阵中 它是该颜色最右上方的那个点 的矩阵的数量
枚举单点复杂度O(n^2)，则我们需要在O(n)的时间内求出贡献设矩阵形式为 [h,w]*[l,r]，则对于某点(x,y)，至少要求 h <= x, w >= x, l <= y, r >= y
对于下边界 w ，可发现没有限制，取值范围为 [x,n]
对于上边界 h ，为该列上与(x,y)颜色相同的上一个节点
对于左右边界 l,r，可发现其与上边界相关：当取上边界为h时，要求 [h,x+1] * [l,r] 中不包含同颜色的点
还可以发现，随着h的减小，l单调递增，r单调递减
即同一列只有最下边一个点有用
故可以先处理出每一个 h 对应的 l,r 的最小（最大）值，O(n) 枚举上边界 h （或者在枚举的时候O(1)更新）具体做法是维护每种颜色的每一列的最下面的点的行号
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 10005;
int row[N][105];
int l[105], r[105];
int t, n, m;
LL ans;
void solve(int x, int y, int c)
{
    int i, h;
    for (i = 1; i <= x; i++) l[i] = 0, r[i] = m+1;
    for (i = 1; i < y; i++) l[row[c][i]] = i;
    for (i = m; i > y; i--) r[row[c][i]] = i;
    h = row[c][y];
    for (i = x-1; i > h; i--)
        l[i] = max(l[i], l[i+1]), r[i] = min(r[i], r[i+1]);
    for (i = x; i > h; i--)
        ans += (LL)(r[i]-y) * (y-l[i]) * (n-x+1);
}
int main()
{
    int i, j, col;
    scanf("%d", &t);
    while (t--)
    {
        memset(row, 0, sizeof(row));
        scanf("%d%d", &n, &m);
        ans = 0;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++)
            {
                scanf("%d", &col);
                solve(i, j, col);
                row[col][j] = i;
            }
        LL all = (LL)n*(n+1)/2*m*(m+1)/2;
        printf("%.9f\n", (double)ans/all);
    }
}