考虑求最大异或生成树的分治做法，每次按最高位分成$V_0,V_1$两个集合（如果不行，那么这一层就不管）。
然后再中间选一条最小边连接两个集合。两个集合分别再分治下去。
现在我们希望求到中间这条最小边的边权的期望。
直接求不好求，考虑换个方式统计。
设$h_{n,m,bit,lim}$表示在第$bit + 1$位将图分成$X,Y$两个集合，其中$|X| = n, |Y| = m$，两个集合间的所有边的边权都大于等于$lim$的方案数（或概率）。
转移的时候讨论一下
- $lim$在第$bit$位为0
- 如果$X,Y$中的点在$bit$位，一个集合中全为0，另一个集合中全为1，那么剩下的位可以任意填。
- 否则枚举$X,Y$中分别有多少个点在第$bit$位为1，然后将集合又分为$X_0, X_1, Y_0, Y_1$，显然最小边连在$X_0, Y_0$之间或者$X_1,Y_1$之间，这是一个子问题，可以通过这个子问题的答案转移，再乘上组合数。
- $lim$在第$bit$位为1
- 此时$X,Y$中的点在$bit$位一定满足一个集合中全为0，另一个集合中全为1，直接通过它转移。
统计期望或每种情况的边权和的时候做一个和就求出来了。
设$f_{i, j}$表示有一个$i$个点的完全图，每个点的权值是$[0, 2^{j})$中的随机整数时的所有方案的答案和。
显然能通过枚举$X_1$集合的大小来转移。
复杂度令人绝望（据说常数小就能卡过去）。但是$n,m$都比较小，打个表交上去就过了。
Code
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
typedef bool boolean; const int N = , M = , S = << M;
const int Mod = ; int add(int a, int b) {
return ((a += b) >= Mod) ? (a - Mod) : (a);
} int sub(int a, int b) {
return ((a -= b) < ) ? (a + Mod) : (a);
} int mul(int a, int b) {
return a * 1ll * b % Mod;
} int qpow(int a, int p) {
int pa = a, rt = ;
for ( ; p; p >>= , pa = mul(pa, pa))
if (p & )
rt = mul(rt, pa);
return rt;
} int inv(int a, int n) {
return qpow(a, n - );
} int n, m;
int f[N][N];
int comb[N][N];
int pow2[N * M];
int h[N][N][M][S]; inline void init() {
scanf("%d%d", &n, &m);
comb[][] = ;
for (int i = ; i <= n; i++) {
comb[i][] = comb[i][i] = ;
for (int j = ; j < i; j++)
comb[i][j] = add(comb[i - ][j - ], comb[i - ][j]);
}
pow2[] = ;
for (int i = ; i <= (n + ) * (m + ) + ; i++)
pow2[i] = add(pow2[i - ], pow2[i - ]);
} int dp(int n, int m, int bit, int lim) {
if (!bit)
return !lim;
if (!n || !m)
return pow2[(n + m) * bit];
int& rt = h[n][m][bit][lim];
if (~rt)
return rt;
if ((lim >> (bit - )) & ) {
rt = dp(n, m, bit - , lim ^ ( << (bit - )));
rt = add(rt, rt);
} else {
rt = pow2[(n + m) * (bit - ) + ];
for (int x = ; x <= n; x++)
for (int y = ; y <= m; y++) {
if ((!x && y == m) || (!y && x == n))
continue;
int a = dp(x, y, bit - , lim);
int b = dp(n - x, m - y, bit - , lim);
rt = add(rt, mul(mul(a, b), mul(comb[n][x], comb[m][y])));
}
}
return rt;
} int g(int n, int m, int bit) {
int rt = ;
for (int i = ; i < pow2[bit]; i++)
rt = add(rt, dp(n, m, bit, i));
// cerr << n << " " << m << " " << rt << " " << bit << '\n';
return rt;
} inline void solve() {
memset(h, -, sizeof(h));
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++) {
int& val = f[i][j];
val = add(f[i][j - ], f[i][j - ]);
for (int cnt = , tmp; cnt < i; cnt++) {
tmp = mul(f[cnt][j - ], pow2[(i - cnt) * (j - )]);
tmp = add(tmp, mul(f[i - cnt][j - ], pow2[cnt * (j - )]));
tmp = add(tmp, g(cnt, i - cnt, j - ));
tmp = add(tmp, pow2[(i + ) * (j - )]);
// printf("tmp %d %d %d= %d\n", i, j, cnt, tmp);
val = add(val, mul(tmp, comb[i][cnt]));
}
// printf("f[%d][%d] = %d\n", i, j, f[i][j]);
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
printf("\tf[%d][%d] = %d;\n", i, j, mul(f[i][j], inv(pow2[i * j], Mod)));
}
}
} int main() {
freopen("young.txt", "w", stdout);
init();
solve();
return ;
}