思路就是求某种颜色对于答案的贡献，然后累加起来即可。
考虑颜色c对答案的贡献，即至少包含一个c颜色格子的矩阵的数目。现在的问题是我们如何不重复不遗漏的统计个数。先排个序（行号升序，列号升序，实际上也就是从左往右从上往下的考虑）。把每个合法的矩阵算在序最小的那个关键点头上，这样就可以保证不重复，不遗漏。那么我们再找包含第一个关键点的矩阵的时候，显然没有任何限制，只需要包含这个点就行了。找第二个关键点的矩阵的时候，不能包含第一个点……找第i个关键点决定的矩阵的时候，不能包含1..i-1这i-1个点。
暴力计数即可，代码如下：
#include <bits/stdc++.h> using namespace std; typedef long long int LL; const int MOD = 998244353; const int MAX_N = 105; const int INF = 0x3f3f3f3f; int col[MAX_N][MAX_N]; int main() { //freopen("test.txt", "r", stdin); //freopen("out.txt", "w", stdout); cin.sync_with_stdio(false); int T; cin >> T; while (T--) { int n, m; cin >> n >> m; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin >> col[i][j]; LL ans = 0; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { int c = col[i][j]; int l = 0, r = m + 1; for (int k=i; k>=1; k--) { for (int t=j; t>=1; t--) if (col[k][t] == c) { if (k == i && t == j) continue; l = max(l, t); break; } for (int t=j; t<=m&&k<i; t++) if (col[k][t] == c) { if (k == i && t == j) continue; r = min(r, t); break; } ans += (j - l) * (r - j) * (n - i + 1LL); } } LL cnt = n * (n - 1) * m * (m - 1) / 4 + n * m * (m + n) / 2; printf("%.9f\n", ans * 1.0 / cnt); } return 0; }
