非常神奇的一个套路......首先min-max容斥一波，变成枚举子集然后求所有子集min的期望。
一个子集的期望怎么求？我们可以求出所有的r = 2nm - n - m个选法中能够选到这个子集的方案数k，那么概率就是k / r，则期望是r / k。
发现子集数量上天了......但是这个方案数k十分之小。
于是我们非常神奇的转换思路。
求出对于每个k，有多少个子集满足恰有k种选法能够选到。
这样我们就能够把k当成一维状态，进行状压DP。压轮廓线上的点是否选入子集，一格一格转移。
每种选法在右边/下边的格子统计。每次枚举当前这格选不选，然后观察方案数是否增加。
如果选了一个格子，集合数量改变，要乘一个-1作为系数。
1 #include2 3 typedef long long LL; 4 const int N = 110, MO = 998244353; 5 6 int G[N][N], n, m, f[2][1200][200], inv[1200]; 7 char str[N]; 8 9 inline void add(int &a, const int &b) {10 a = a + b;11 while(a >= MO) a -= MO;12 while(a < 0) a += MO;13 return;14 }15 16 inline void out(int x) {17 for(int i = 0; i < m; i++) printf("%d", (x >> i) & 1);18 return;19 }20 21 int main() {22 23 scanf("%d%d", &n, &m);24 for(int i = 1; i <= n; i++) {25 scanf("%s", str + 1);26 for(int j = 1; j <= m; j++) {27 G[j][i] = (str[j] == '*');28 }29 }30 std::swap(n, m);31 32 /// input over33 34 int lm = (1 << m), up = 2 * n * m - n - m;35 f[0][0][0] = -1;36 for(int i = 1; i <= n; i++) {37 for(int j = 0; j < m; j++) {38 /// pos (i, j)39 int p = (i - 1) * m + j;40 41 for(int w = 0; w <= up; w++) {42 for(int s = 0; s < lm; s++) {43 f[(p + 1) & 1][w][s] = 0;44 }45 }46 47 for(int w = 0; w <= up; w++) {48 for(int s = 0; s < lm; s++) {49 if(!f[p & 1][w][s]) continue;50 //printf("f (%d %d) w=%d ", i, j, w); out(s); printf(" = %d \n", f[p][w][s]);51 int c = f[p & 1][w][s], temp = 0;52 if(j) temp += (s >> (j - 1)) & 1;53 if(i > 1) temp += (s >> j) & 1;54 add(f[(p + 1) & 1][w + temp][s & (~(1 << j))], c); /// not choose55 if(G[i][j + 1]) {56 add(f[(p + 1) & 1][w + (i > 1) + (j > 0)][s | (1 << j)], -c); /// choose57 }58 }59 }60 }61 }62 //printf("\n");63 inv[0] = inv[1] = 1;64 for(int i = 2; i <= up; i++) {65 inv[i] = 1ll * inv[MO % i] * (MO - MO / i) % MO;66 }67 int ans = 0, p = n * m;68 for(int w = 1; w <= up; w++) {69 for(int s = 0; s < lm; s++) {70 add(ans, 1ll * f[p & 1][w][s] * inv[w] % MO * up % MO);71 //printf("ed : w=%d ", w); out(s); printf(" = %d \n", f[p][w][s]);72 }73 }74 printf("%d\n", ans);75 return 0;76 }
[update]注意到这个DP数组中的那个s维，一定是“*”的子集。否则不会转移，为0，没有意义。
not choose那个转移表示当前不是*或者不选，当前这里覆盖上面那个*或左边那个*。
choose表示这里是*且加入集合，有两种摆法覆盖它，同时多了一个*导致要乘一个-1。