【题意】
给你一个矩阵，问随机一个子矩阵的颜色个数的期望数。
【Solution】
期望转计数问题。
考虑这样一种计数方式，对于任意一个子矩阵中的某一个颜色c，我们只在其从左往右，从上往下的第一次出现计算它。
于是反过来，我们可以计算每一个格子在多少个子矩阵中被计算了。
如上图所示，如果我们要计算浅绿色格子，则四个深绿色格子不能参与计算。
通过维护每个颜色在每一行最后一次出现的位置，我们可以维护右边的x的轮廓，进而维护当左边界固定为某一列时，上边界和下边界的位置。
这个维护可以用暴力维护，复杂度是$(n^3)$，常数不是特别大，比标程的$O(n^4 / 13)$优。
【Code】
耗时:124 ms
内存:6256 K
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
int mp[maxn][maxn];
int ls[maxn * maxn][maxn];
//int up[maxn * maxn][maxn], dn[maxn * maxn][maxn];
int pref[maxn], suff[maxn], upper[maxn], lower[maxn];
long long ans = 0;
int n, m;
double sol()
{
ans = 0;
memset(ls, 0, sizeof ls);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &mp[i][j]);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
int co = mp[i][j];
memset(upper, 0, sizeof upper);
memset(lower, 0x3f, sizeof lower);
memset(pref, 0, sizeof pref);
memset(suff, 0, sizeof suff);
pref[j] = ls[co][j];
for (int k = j - 1; k >= 1; k--)
pref[k] = max(pref[k + 1], ls[co][k]);
for (int k = 0; k <= j; k++)
upper[pref[k]] = k + 1;
upper[i] = max(upper[i], 1);
for (int k = i - 1; k >= 1; k--)
upper[k] = max(upper[k], upper[k + 1]);
//
suff[j] = ls[co][j];
for (int k = j + 1; k <= m; k++)
suff[k] = max(suff[k - 1], ls[co][k]);
for (int k = m; k >= j; k--)
lower[suff[k]] = k - 1;
lower[i] = min(lower[i], m);
for (int k = i - 1; k >= 1; k--)
lower[k] = min(lower[k], lower[k + 1]);
for (int k = 1; k <= i; k++)
{
if (upper[k] > j || lower[k] < j) continue;
int up = j - upper[k] + 1;
int dn = lower[k] - j + 1;
ans += up * dn * (n - i + 1);
}
ls[co][j] = i;
}
}
long long tot = (n + 1ll) * (m + 1ll) * n * m;
return 4. * ans / (tot);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
printf("%.9f\n", sol());
return 0;
}