UOJ 422 [集训队作业2018] 小Z的礼物 min-max容斥 期望 轮廓线dp

时间：2022-08-20 21:48:03

LINK：小Z的礼物

太精髓了 我重学了一遍min-max容斥 重写了一遍按位或才写这道题的。

还是期望多少时间可以全部集齐.

相当于求出 \(E(max(S))\)表示最后一个出现的期望时间.

根据min-max容斥 显然有 \(E(max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(min(T))\)

对于这道题 要求出所有的T 直接\(2^{cnt}\)枚举不太现实。

但是我们仍要对每个集合求出其概率.

考虑从矩阵上进行dp来进行压缩状态 那么因为一个格子的选择之和周围的格子的有关可以简单的记轮廓线来进行dp.

需要记录一下到底有多少个格子是有效的 代价正负一可以直接累计到状态里不需要多开一维.

然后就做完了.

值得一提的细节是 这个min-max容斥不包含空集.

code
//#include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cctype>

#include<queue>

#include<deque>

#include<stack>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 10000000000000000ll

#define inf 1000000000

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007ll

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-10

#define sq sqrt

#define S second

#define F first

#define mod 998244353

using namespace std;

char *fs,*ft,buf[1<<15];

inline char gc()

{

	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

	RE int x=0,f=1;RE char ch=gc();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}

	return x*f;

}

const int MAXN=110;

int n,m;

char a[MAXN][MAXN];

int inv[1200];

int f[2][1<<6][1200];

inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}

int main()

{

	//freopen("1.in","r",stdin);

	gt(n);gt(m);

	rep(1,n,i)scanf("%s",a[i]+1);

	int sum=2*n*m-n-m;

	int maxx=1<<n;--maxx;

	int u=0;inv[1]=1;

	f[u][0][0]=mod-1;

	rep(2,sum,i)inv[i]=(ll)inv[mod%i]*(mod-mod/i)%mod;

	rep(1,m,j)

	{

		rep(1,n,i)

		{

			u=u^1;

			memset(f[u],0,sizeof(f[u]));

			rep(0,maxx,k)

			{

				//put(f[u^1][k][1]);

				rep(0,sum,l)if(f[u^1][k][l])

				{

					int s=k&(maxx^(1<<(i-1)));

					add(f[u][s][l],f[u^1][k][l]);

					if(a[i][j]=='*')

					{

						s=k|(1<<(i-1));

						int cnt=0;

						if(j>1&&!(k&(1<<(i-1))))++cnt;

						if(i>1&&!(k&(1<<(i-2))))++cnt;

						if(i<n)++cnt;if(j<m)++cnt;

						add(f[u][s][l+cnt],mod-f[u^1][k][l]);

					}

				}

			}

		}

	}

	int ans=0;

	rep(0,maxx,i)rep(1,sum,j)add(ans,(ll)f[u][i][j]*inv[j]%mod);

	ans=(ll)ans*sum%mod;put(ans);

	return 0;

}

相关文章