首页 > 代码库 > bzoj4671: 异或图
bzoj4671: 异或图
Description
定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与
G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中.
现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异
或为一个连通图?
Input
第一行为一个整数s, 表图的个数.
接下来每一个二进制串, 第 i 行的二进制串为 gi, 其中 gi 是原图通过以下伪代码转化得
到的. 图的结点从 1 开始编号, 下面设结点数为 n.
Algorithm 1 Print a graph G = (V, E)
for i = 1 to n do
for j = i + 1 to n do
if G contains edge (i, j) then
print 1
else
print 0
end if
end for
end for
2 ≤ n ≤ 10,1 ≤ s ≤ 60.
Output
输出一行一个整数, 表示方案数
解异或方程组可以求出每种连通情况（用最小表示法表示连通性，要求不同标号的点严格不连通，相同标号的点任意）的方案数
容斥一下可以得到答案
#include<cstdio>#include<cstring>typedef unsigned long long u64;char s[75];int n=1,m,v[75],xp=0;u64 ans=0,fac[75],x[75],e[75];void dfs(int w,int mx=0){ if(w==n){ xp=0; for(int i=0,p=0;i<n;++i) for(int j=i+1;j<n;++j,++p)if(v[i]!=v[j])x[xp++]=e[p]; int t=0; while(xp<m)x[xp++]=0; for(int i=0,w=0;i<m;++i){ if(~x[w]>>i&1){ for(int j=w+1;j<xp;++j)if(x[j]>>i&1){ x[w]^=x[j]; break; } } if(x[w]>>i&1){ for(int j=w+1;j<xp;++j)if(x[j]>>i&1)x[j]^=x[w]; ++w; }else ++t; } if(mx&1)ans+=fac[mx-1]<<t; else ans-=fac[mx-1]<<t; return; } for(int i=0;i<=mx;++i){ v[w]=i; dfs(w+1,mx+(i==mx)); }}int main(){ scanf("%d",&m); for(int t=0,l;t<m;++t){ scanf("%s",s); l=strlen(s); while(n*(n-1)/2<l)++n; for(int i=0,p=0;i<n;++i) for(int j=i+1;j<n;++j,++p)if(s[p]==‘1‘)e[p]|=1llu<<t; } for(int i=fac[0]=1;i<=n;++i)fac[i]=fac[i-1]*i; dfs(0); printf("%lld",ans); return 0;}
bzoj4671: 异或图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。