非常神奇的一个套路......首先min-max容斥一波，变成枚举子集然后求所有子集min的期望。
一个子集的期望怎么求？我们可以求出所有的r = 2nm - n - m个选法中能够选到这个子集的方案数k，那么概率就是k / r，则期望是r / k。
发现子集数量上天了......但是这个方案数k十分之小。
于是我们非常神奇的转换思路。
求出对于每个k，有多少个子集满足恰有k种选法能够选到。
这样我们就能够把k当成一维状态，进行状压DP。压轮廓线上的点是否选入子集，一格一格转移。
每种选法在右边/下边的格子统计。每次枚举当前这格选不选，然后观察方案数是否增加。
如果选了一个格子，集合数量改变，要乘一个-1作为系数。
1 #include <bits/stdc++.h> 2 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 over 33 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 ", 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 choose 55 if(G[i][j + 1]) { 56 add(f[(p + 1) & 1][w + (i > 1) + (j > 0)][s | (1 << j)], -c); /// choose 57 } 58 } 59 } 60 } 61 } 62 //printf(" "); 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 ", f[p][w][s]); 72 } 73 } 74 printf("%d ", ans); 75 return 0; 76 }
[update]注意到这个DP数组中的那个s维，一定是“*”的子集。否则不会转移，为0，没有意义。
not choose那个转移表示当前不是*或者不选，当前这里覆盖上面那个*或左边那个*。
choose表示这里是*且加入集合，有两种摆法覆盖它，同时多了一个*导致要乘一个-1。