小Z的礼物[集训队作业2018]

发表于 分类于

题目链接

uoj

题解

可以发现，最大值这种东西一般都不太好做。考虑转换成最小值（即第一次被覆盖）。

由期望下的Min-Max容斥得到：

$$E(\max(S))=\sum_{T\in S,T\not= \varnothing }E(\min(T))(-1)^{|T|+1}$$

其中 $E(\min(T))$ 表示 $T$ 集合中物品中的其中一个，第一次被覆盖的期望时间。

设选一次相邻的两个物品中至少含有一个 $T$ 集合中物品的概率为 $P$。

设 $f(i)$ 表示前 $i$ 次覆盖都没有覆盖成功的概率，显然有：$f(i)=(1-P)^i$。

那么 $T$ 集合中物品第一次被覆盖的期望时间为：$\sum_{i=0}^{\infty} f(i)=\sum_{i=0}^{\infty}(1-P)^i$

由于 $P\not =0$，那么 $1-P<1$，则上式收敛，那么有：$E(\min (T))=\frac{1}{1-(1-P)}=\frac{1}{P}$

这个 $P=\frac{W_T}{2nm-n-m}$，其中 $W_T$ 为选两个相邻物品至少包含一个 $T$ 集合中物品的方案数。

$n$ 这么小，那么就可以考虑轮廓线DP了。

设 $f_{i,j,s,k}$ 表示考虑到第 $i$ 列第 $j$ 行，状态为 $s$，$W_T=k$ 的容斥系数和。

最后的答案为 $\sum_{s}\sum_{k}\frac{f_{m,n,s,k}\times (2nm-n-m)}{k}$。

这个DP很好转移，考虑4个方向的情况就好了。

时间复杂度 $O(2^nn^2m^2)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y){y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;return ans;}
int cnt,sum,d,t;
int n,m;
char S[7][105];
ll f[2][70][1205];
inline bool bit(int x,int k){return (x>>k)&1;}
int main()
{
    n=read(); m=read();
    fo(i,1,n) scanf("%s",S[i]+1);
    cnt=1<<n; sum=2*n*m-n-m;
    f[d=0][0][0]=mod-1;
    int w;
    fo(i,1,m)
        fo(j,1,n)
        {
            d=1-d;
            memset(f[d],0,sizeof(f[d]));
            fo(s,0,cnt-1)
                fo(k,0,sum)
                    if(f[d^1][s][k])
                    {
                        t=s>>1;
                        f[d][t][k]=Add(f[d][t][k],f[d^1][s][k]);
                        t=t|(1<<(n-1));
                        if(S[j][i]=='*')
                        {
                            w=0;
                            if(i>1&&!bit(s,0))   w++;
                            if(j>1&&!bit(s,n-1)) w++;
                            if(j<n) w++; if(i<m) w++;
                            f[d][t][k+w]=Dec(f[d][t][k+w],f[d^1][s][k]);
                        }
                    }
        }
    ll ans=0;
    fo(i,0,cnt-1)
        fo(j,0,sum)
            ans=Add(ans,Mul(f[d][i][j],Pow(j,mod-2)));
    printf("%lld",Mul(sum,ans));
    return 0;
}