ZOJ 4098 Defense Plan

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4098

题意：有 $n$ 个点， $m$ 对互斥关系 $(x,y)$ 表示选了 $x$ 就不能选 $y$ ,选了 $y$ 就不能选 $x$ ，一个可行点集的价值是这些点价值的乘积，求所有可行方案的方差。

思路：我们先把方差公式化简一下，可以得到

S^2=\frac{\sum_{i=1}^{k}x_i^2}{k}-\overline{x}^2

所以我们只要知道 $\sum_{i=1}^{k}x_i$ , $\sum_{i=1}^{k}x_i^2$ , $k$ 即可算出答案，考虑到 $n$ 有 $40$ ，我们折半搜出两边的答案。考虑如何整合两边的答案，其实就是两边的集合拼起来以后依然是一个合法集合，所以我们第二遍搜到一个可行集合的时候，可以根据互斥关系求出对于前半个点集可选的点集，然后这个点集的子集都是满足条件的，我们只要知道这个点集的所有子集和然后去乘第二遍搜到的答案就可以了，求一个状态的所有子集和，可以再第一遍搜完以后高维前缀和优化，然后就可以通过了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
	x=0;int f=0;char ch=getchar();
	while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
	while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return x=f?-x:x;
}
const int N=40+10;
const int P=1e9+7;
int n,m,i,x,y,A,B,C,status,a[N],w[N],g2[N],g3[N],dp[(1<<22)+10],dp2[(1<<22)+10],dp3[(1<<22)+10];
ll g[N];
inline void up(int &a,int b){a+=b;if(a>=P)a-=P;}
int fexp(int a,int n){
	int res=1;
	while (n){
		if (n&1) res=1LL*res*a%P;
		a=1LL*a*a%P;
		n>>=1;
	}
	return res;
}
void dfs(int x,int tot,int val,int val2,int SS,int S){
	if (x==tot+1){
		up(dp[SS],val);
		up(dp2[SS],1);
		up(dp3[SS],val2);
		return;
	}
	dfs(x+1,tot,val,val2,SS,S);
	if (!(S>>x&1)) dfs(x+1,tot,1LL*val*w[x]%P,1LL*val2*a[x]%P,SS|(1<<x),(S|g2[x])|(1<<x));
}
void dfs2(int x,int tot,int val,int val2,int SS,int S){
	if (x==tot+1){
		int S2=0;
		for (int i=1;i<=n-n/2;++i)if(SS>>i&1){
			for (int j=1;j<=n/2;++j)if(g[i+n/2]>>j&1){
				S2|=1<<j;
			}
		}
		for (int j=1;j<=n/2;++j){
			S2^=1<<j;
		}
		up(A,1LL*val*dp[S2]%P);
		up(B,dp2[S2]);
		up(C,1LL*val2*dp3[S2]%P);
		return;
	}
	dfs2(x+1,tot,val,val2,SS,S);
	if (!(S>>x&1)) dfs2(x+1,tot,1LL*val*w[x+n/2]%P,1LL*val2*a[x+n/2]%P,SS|(1<<x),(S|g3[x])|(1<<x));
}
int main(){
	read(n),read(m);
	for (i=1;i<=n;++i) read(w[i]),a[i]=1LL*w[i]*w[i]%P;
	for (i=1;i<=m;++i){
		read(x),read(y);
		if (x<=n/2 && y<=n/2) g2[x]|=1<<y,g2[y]|=1<<x;
		else if (x>n/2 && y>n/2) g3[x-n/2]|=1<<(y-n/2),g3[y-n/2]|=1<<(x-n/2);
		g[x]|=1LL<<y,g[y]|=1LL<<x;
	}
	dfs(1,n/2,1,1,0,0);
	for (i=0;i<=n/2;++i){
        for (status=0;status<(1<<(n/2+1));++status){
            if (status&(1<<i)){
            	up(dp[status],dp[status^(1<<i)]);
        		up(dp2[status],dp2[status^(1<<i)]);
        		up(dp3[status],dp3[status^(1<<i)]);
        	}
        }
    }
	dfs2(1,n-n/2,1,1,0,0);

	int ans=1LL*C*fexp(B,P-2)%P;
	A=1LL*A*fexp(B,P-2)%P;
	A=1LL*A*A%P;
	ans=(ans-A)%P;
	if (ans<0) ans+=P;
	printf("%d\n",ans);
	return 0;
}

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.