【洛谷U20626】gemo 容斥 FWT 高斯消元

2018/03/06 15:23
阅读数 9

题目大意

  给你一个无向图,有$m$个询问,每次给你一个点$x$和一个点集$S$,问你从$x$开始走,每次从一个点随机的走到与这个点相邻的点,问你访问$S$中每个点至少一次的期望步数是多少。

  $n\leq 18,m\leq 100000$

题解

  有个东西叫min-max容斥: $$ \max(S)=\sum_{T\subseteq S,T\neq \varnothing}{(-1)}^{|T|+1}\min(T) $$

  这道题中,$\min(S)$是从点$x$开始走,走到$S$中任意一个点的期望步数。$\max(S)$是从$x$开始走,走完$S$中全部点的期望步数。

  我们先枚举所有$S$,用高斯消元算出$\min(S)$。

  总共有$2^n$个集合,消一次是$O(n^3)$的。

  这样就算出了所有起点为$i$,遍历$S$中每个点至少一次的期望步数$f_{i,S}$

  然后带入这个式子里,用FWT算出$\max(S)$。

  总共有$n$个不同的起点,FWT一次是$O(n2^n)$的。

  所以总的时间复杂度是$O(n^32^n)$的。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const ll p=998244353;
vector<int> g[20];
int n,m;
int d[20];
int a[19][20];
ll inv[10010];
int c[10010];
ll fp(ll a,ll b)
{
	ll s=1;
	for(;b;b>>=1,a=a*a%p)
		if(b&1)
			s=s*a%p;
	return s;
}
int f[19][1<<18];
int bitcnt[1<<18];
void add(int &a,int b)
{
	if((a+=b)>p)
		a-=p;
}
void fwt(int *a,int n)
{
	int i,j,k;
	for(i=2;i<=1<<n;i<<=1)
		for(j=0;j<1<<n;j+=i)
			for(k=j;k<j+i/2;k++)
				add(a[k+i/2],a[k]);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("gemo.in","r",stdin);
	freopen("gemo.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	int x,y;
	int i,j;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		d[x]++;
		d[y]++;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	inv[0]=inv[1]=1;
	for(i=2;i<=10000;i++)
		inv[i]=-p/i*inv[p%i]%p;
	ll v;
	int k;
	int l;
	int all=(1<<n)-1;
	bitcnt[0]=0;
	for(i=1;i<all;i++)
		bitcnt[i]=bitcnt[i>>1]+(i&1);
	for(l=1;l<all;l++)
	{
		memset(a,0,sizeof a);
		for(i=1;i<=n;i++)
		{
			a[i][i]=1;
			if(l&(1<<(i-1)))
				continue;
			a[i][n+1]=1;
			for(auto v:g[i])
				a[i][v]=-inv[d[i]];
		}
		for(i=1;i<=n;i++)
		{
			for(j=i;j<=n;j++)
				if(a[i][j])
					break;
			if(j>n)
				continue;
			if(i!=j)
				for(k=i;k<=n+1;k++)
					swap(a[i][k],a[j][k]);
			if(a[i][i])
			{
				v=fp(a[i][i],p-2);
				for(j=i;j<=n+1;j++)
					a[i][j]=a[i][j]*v%p;
			}
			for(j=1;j<=n;j++)
				if(i!=j&&a[j][i])
				{
					v=a[j][i];
					for(k=i;k<=n+1;k++)
						a[j][k]=(a[j][k]-a[i][k]*v)%p;
				}
		}
		for(i=1;i<=n;i++)
			f[i][l]=a[i][n+1];
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<all;j++)
		{
			if(!(bitcnt[j]&1))
				f[i][j]=-f[i][j];
			if(f[i][j]<0)
				f[i][j]+=p;
		}
		fwt(f[i],n);
	}
	int m;
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&x);
		int s=0;
		for(j=1;j<=x;j++)
		{
			scanf("%d",&y);
			s|=1<<(y-1);
		}
		scanf("%d",&y);
		printf("%d\n",f[y][s]);
	}
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部