Codeforces 870E Points, Lines and Ready-made Titles

题面在这里

考虑两种方案不一样当且仅当某一行或某一列的情况不一样

熟悉的套路……对于每个点,连接它所在的行和列

对于每条边,可以把权赋给一个端点或者什么都不做

方案不同其实是图中点的01串不同

那么如果一个连通块是树,有\(2^{size}-1\)的贡献,否则有\(2^{size}\)的贡献

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn=200005,MOD=1e9+7;
int n,x[maxn],y[maxn],a[maxn],b[maxn],pw[maxn];
int fa[maxn],siz[maxn],ed[maxn];
inline int getfa(int x){
return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]),a[++a[0]]=x[i],b[++b[0]]=y[i];
sort(a+1,a+1+a[0]); a[0]=unique(a+1,a+1+a[0])-a-1;
sort(b+1,b+1+b[0]); b[0]=unique(b+1,b+1+b[0])-b-1;
for (int i=1;i<=n;i++)
x[i]=lower_bound(a+1,a+1+a[0],x[i])-a,y[i]=lower_bound(b+1,b+1+b[0],y[i])-b;
pw[0]=1;
for (int i=1;i<=a[0]+b[0];i++) fa[i]=i,siz[i]=1,pw[i]=pw[i-1]*2%MOD;
for (int i=1;i<=n;i++){
int fx=getfa(x[i]),fy=getfa(y[i]+a[0]);
if (fx==fy) ed[fx]++;
else fa[fx]=fy,siz[fy]+=siz[fx],ed[fy]+=ed[fx]+1;
}
ll ans=1;
for (int i=1;i<=a[0]+b[0];i++)
if (getfa(i)==i)
if (ed[i]==siz[i]-1) (ans*=pw[siz[i]]-1)%=MOD;
else (ans*=pw[siz[i]])%=MOD;
printf("%lld",(ans+MOD)%MOD);
return 0;
}