[题解][bzoj4671]异或图

再不写题解估计就又双叒叕忘了斯特林反演怎么写了 题目意思应该很清楚了 那么我们现在来考虑怎么搞这个东西 不妨设$f(i)$表示至少有i个联通块的方案数,$g(i)$表示恰好有i个联通块方案数(注意这里的至少不保证每个方案都被算一次) 那么我们似乎可以得到这样一个显而易见的式子就是，其中m表示图的点数 $$f(n)=\sum_{i=n}^{m}g(i)S_{i}^{n}$$ 其中$S_{i}^{n}$表示第二类斯特林数，其实就是考虑每一个大于n的方案被算了多少次，那么就是把i个联通块划分为n组的方案数，自然就是斯特林数了 那么我们稍稍变化一下就可以得到一个正常一点的容斥式子 $$g(n)=f(n)-\sum_{i=n+1}^{m}g(i)S_{i}^{n}$$ 当然大多数网上的题解不是这么写的，因为我们只需要求出$g(1)$因此我们可以考虑一下每个$f(i)$对$g(1)$的贡献，通过打表可以得到 $$g(1)=\sum_{i=1}^{m}f(i)(-1)^{i-1}(i-1)!$$ 当然你会发现上面做法的优越之处就在于我们可以同时输出$g(1)$~$g(n)$ (出题人真的这么干了可能会被打死) 那么我们可以考虑怎么算$f(i)$，首先我们先对这n个点dfs出一个集合划分来，具体点讲就是每个点有两种选择，一种是自己新开一个集合或者是加入之前已有的一个集合 当我们dfs出来这个集合划分之后，我们钦定不同集合的边必须被异或掉，这样的话这中方案至少有i个联通块了 现在唯一的问题就是如何让各个联通块之间没有任何边 具体来讲我们把跨越不同联通块的边都拿出来，然后每张图就变成了一个01串，现在我们希望选一些数字使得异或和为0 假设这个数字集合一共有x个线性基n个数字，由于线性基的特点是其中任意一个数字不可能被表示成其他数字，所以答案不可能是线性基的一个子集，既然不可能是子集就一定包含其他元素，设最终方案中非线性基元素的异或和是v，那么v可以被线性基唯一的表示出来，所以方案数有且仅有$2^{n-x}$种，这样的话容斥的底层计数就被我们解决了，然后如果这个集合划分一共有k个集合我们就将他贡献到$f(k)$当中去，所以一开始说$f(k)$不是严格的至少出现k个联通块的方案数，因为这个xjb的计数策略明摆着会重复，不过没关系，我们推出来的容斥系数还是对的 然后就是dfs套个线性基就做完了这题 上代码~ ```C /************************************************************** Problem: 4671 User: shadowice1984 Language: C++ Result: Accepted Time:9388 ms Memory:828 kb ****************************************************************/ #include<cstdio> #include<algorithm> using namespace std;const int N=65;typedef unsigned long long ll; int n;int m;int s;ll gr[N];int col[N];ll ans;ll fac[N];char mde[N]; struct linebas { ll bas[N]; inline void ins(ll x) { for(int i=m-1;i>=0;i--) if((x>>i)&1){if(bas[i]==0){bas[i]=x;break;}else x^=bas[i];} } inline int cot(){int r=0;for(int i=0;i<m;i++)r+=(bas[i]!=0);return r;} inline void clr(){for(int i=0;i<m;i++)bas[i]=0;} }lb; inline void dfs(int u,int ct) { if(u==n+1) { ll flt=0;lb.clr(); for(int i=1,nu=0;i<=n;i++) for(int j=i+1;j<=n;j++,nu++)if(col[i]!=col[j])flt|=(1LL<<nu); for(int i=1;i<=s;i++)lb.ins(flt&gr[i]); if((ct-1)&1)ans-=fac[ct-1]*(1LL<<(s-lb.cot())); else ans+=fac[ct-1]*(1LL<<(s-lb.cot()));return; }col[u]=ct+1;dfs(u+1,ct+1); for(int i=1;i<=ct;i++)col[u]=i,dfs(u+1,ct); } int main() { fac[0]=1;for(int i=1;i<=10;i++)fac[i]=fac[i-1]*i; scanf("%d",&s);int len; for(int i=1;i<=s;i++) { scanf("%s",mde+1);len=1;for(;mde[len+1]!='\0';len++); for(int j=1;j<=len;j++)gr[i]|=((ll)(mde[j]=='1'))<<(j-1); } for(int i=1;i<=10;i++)if(i*(i-1)/2==len){n=i;break;}m=len; dfs(1,0);printf("%llu",ans);return 0; } ```