2019.2.25 模拟赛T1【集训队作业2018】小Z的礼物

T1：

【集训队作业2018】小Z的礼物

我们发现我们要求的是覆盖所有集合里的元素的期望时间。

设\(t_{i,j}\)表示第一次覆盖第i行第j列的格子的时间，我们要求的是\(max\{ALL\}\)

考虑\(min-max容斥\)。\(max\{S\}=\sum_{S \subset T}(-1) ^{|T|-1}min\{T\}\)

此时我们要求的变为了\(min\{T\}\)，即\(T\)中至少有一个元素被选择的期望。

我们知道当\(T\)中元素被选择的概率为\(P\)时，其期望为\(\frac{1}{P}\)。

因此我们只需要求出符合条件的方案数就行了。

注意到n很小，所以考虑状压轮廓线。

设\(f_{j,k}\)表示轮廓线为\(j\)，方案数为\(k\)的集合个数。

枚举每个i，j是否选入集合并考虑其周围的选择情况转移即可。

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define mod 998244353

#define ll long long

using namespace std;

inline int read() {

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

	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x*f;

}

ll n,m,f[2][200][2000],sum;

char s[10][200];

ll power(ll x,int p) {

	ll ans=1;

	while(p) {

		if(p&1) ans*=x,ans%=mod;

		x*=x;x%=mod;p>>=1;

	}

	return ans;

}

int main() {

	n=read(),m=read();

	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);

	int pre=0;

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum+=(i>1)+(j>1);

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

	for(int i=1;i<=m;i++) {

		for(int j=1;j<=n;j++) {

			for(int S=0;S<(1<<n);S++) {

				for(int k=0;k<=sum;k++) {

					if(!f[pre][S][k]) continue;

					int tmp=pre^1;

					if(s[j][i]=='*') {

						int to=S|(1<<(j-1));

						f[tmp][to][k+(j>1&&!((S>>(j-2))&1))+(i>1&&!((S>>(j-1))&1))+(i<m)+(j<n)]+=-1*f[pre][S][k];

						f[tmp][to][k+(j>1&&!((S>>(j-2))&1))+(i>1&&!((S>>(j-1))&1))+(i<m)+(j<n)]%=mod;

						f[tmp][to][k+(j>1&&!((S>>(j-2))&1))+(i>1&&!((S>>(j-1))&1))+(i<m)+(j<n)]+=mod;

						f[tmp][to][k+(j>1&&!((S>>(j-2))&1))+(i>1&&!((S>>(j-1))&1))+(i<m)+(j<n)]%=mod;

					}

					int to=S&(((1<<n)-1)^(1<<(j-1)));

					f[tmp][to][k]+=f[pre][S][k];

					f[tmp][to][k]%=mod;

					f[pre][S][k]=0;

				}

			}

			pre^=1;

		}

	}

	ll ans=0;

	for(int i=0;i<=sum;i++){

		int tot=0;

		for(int j=0;j<(1<<n);j++) {tot+=f[pre][j][i],tot%=mod;}

		ans=(ans+tot*power(i,mod-2))%mod;

	}

	ans=ans*sum%mod;

	printf("%lld\n",ans);

}

巴特西

2019.2.25 模拟赛T1【集训队作业2018】小Z的礼物

最新文章

热门文章