Ex - Balance Scale
考虑只有>
和<
的情况,相当于给每条边定向,当且仅当成环时不合法,那么方案数就是\(DAG\)的方案数
对于=
,就是将两个点合并
然后对于一般的求\(n\)个点的\(DAG\)的方案数为\(\sum_{i=1}^n (-1)^{i+1}C_n^i2^{i\times(n-i)}\)(枚举入度为\(0\)的点的数量,然后设入度为\(0\)的点的集合为\(A\),所有点的集合为\(N\),那么就是\(A\)内部没有连边。\(A\)向\(N-A\)连边,但是这样不能保证\(N-A\)中没有入度为\(0\)的点,所以容斥)
容斥系数为\((-1)^{i+1}\)的原因:
一般的二项式反演为:\(\sum_{j=i}^n (-1)^{j-i}f(j)\),然后我们在\(DAG\)中\(i=1\),而\((-1)^{i-1}\)和\((-1)^{i+1}\)相等,所以是\((-1)^{i+1}\)
那么这道题是给定的边,且边的方向随意,所以我们考虑枚举独立集(相当于上文中的\(A\)),而普通的求\(DAG\)的边是任意连的,而这道题的边是给定的,所以就没有\(2^{i\times(n-i)}\),即设我们当前总集\(N\),枚举的子集为\(A\)(\(A\)内部属于同一连通块的点全部合并),那么\(A\)向\(N-A\)的连边就是固定的,所以用于转移的是剩下的部分\(N-A\)内部连边的方案数,系数就是\((-1)^{A中独立集的数量+1}\)
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
void add(int &x,int y){ x+=y; if(x>=MOD) x-=MOD; if(x<0) x+=MOD; }
int n,m,f[1<<17],cnt[1<<17],a[400],b[400],fa[18];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<(1<<n);++i) cnt[i]=cnt[i>>1]+(i&1);
for(int s=1;s<(1<<n);++s){
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i)
if((s&(1<<a[i]-1))&&(s&(1<<b[i]-1))){
int x=find(a[i]),y=find(b[i]);
if(x!=y) fa[x]=y,--cnt[s];
}
}
f[0]=1;
for(int s=1;s<(1<<n);++s)
for(int t=s;t;t=((t-1)&s)){
if(cnt[t]&1) add(f[s],f[s^t]);
else add(f[s],-f[s^t]);
// if(t==0) break;
}
printf("%d",f[(1<<n)-1]);
return 0;
}