前言

繼續學習容斥的技巧！

題意簡介

題面鏈接

題目大意

定義兩個無重邊無自環圖$G_1,G_2$的異或為$G_3$($G_1,G_2,G_3$點數都為$n$)
滿足當邊$(u,v)$在$G_1,G_2$中共出現$1$次時$G_3$中有邊$(u,v)$，否則沒有
現在給出$s$個圖，集合$S=\{G_1,G_2,G_3,???G_s\}$問有多少個$S$的子集滿足所有圖的異或圖聯通

數據范圍

$n\le 10,s\le 60$

題解

模擬

模擬大概是$\Theta (2^s{n}^3)$的（如果n和s的數據范圍交換就能過了）
并沒有什么用

正解

我們發現，直接維護是否聯通并不方便
考慮容斥，記$f(x)$為有至少有$x$個聯通塊的方案數，$g(x)$為恰好有$x$個聯通快的方案數
我們發現，求$f(x)$非常方便，我們只要枚舉點集劃分，保證一種劃分中在不同的點集的點間一定沒有邊。我們發現，這樣保證了點集之間一定不連通，但是不保證點集內部聯通，所以就滿足$f(x)$的定義了
我們來列出$f(x)$與$g(x)$的關系

概念：第二類斯特林數是將n個不同的元素拆分成m個集合的方法數目。

那么，就可以得出：$$f(x)=\sum _{i=x}^n\left\{\begin{array}{c}i\\ x\end{array}\right\}g(i)$$
然后就可以斯特林反演得
$$g(x)=\sum _{i=x}^n(?1{)}^{i?x}\left[\begin{array}{c}i\\ x\end{array}\right]f(i)$$
由于我們要求的是$g(1)$
$$g(1)=\sum _{i=1}^n(?1{)}^{i?1}\left[\begin{array}{c}i\\ 1\end{array}\right]f(i)$$
容易發現$\left[\begin{array}{c}i\\ 1\end{array}\right]=(i?1)!$
所以$$g(1)=\sum _{i=1}^n(?1{)}^{i?1}(i?1)!f(i)$$
我們就可以枚舉點集劃分，然后線性基計算方案即可（如果不會計算可以參考我的博客線性基）
貝爾數$B_n$為$n$個點的點集劃分數量
具體$B_0=B_1=1$，當$n>0$時$$B_{n+1}=\sum _{i=0}^n{B}_i$$
所以$B_{10}=115975$
總復雜度是$\Theta (B_n{n}^{4}s)$由于不滿，所以博主滿懷信心的寫了一發
然后發現TLE了，最大數據大概要跑11s+，真是非常的悲慘
原來我用的方法是$\Theta (n^{4}s)$求答案的（具體做法是把$s$個長度為$n^2$的串放到線性基里，重要的是：我沒有壓位，太懶了啊），所以導致復雜度過大
事實上這題可以不用這個復雜度，因為我們發現這個$s$是小于$n^2$的，并且我們發現很多信息都不需要維護，所以我們得到了一個更加優越的$\Theta (n^{2}s)$做法（統計每一位有哪些圖符合條件來計算放進線性基里數的數量，由于此時的線性基是$s$，所以更好壓），那么總復雜度是$\Theta (B_n{n}^{2}s)$、大大減小，就能過了
注：其實算法一是可以用bitset壓一波的，這里列出兩個算法的復雜度
算法一：$\Theta (B_n{n}^{2}s\frac{n^2}{64})$
算法二：$\Theta (B_n{n}^{2}s\frac{s}{64})$
可見算法二復雜度更小并且更方便，所以我最后寫了算法二

斯特林反演

$$f_i=\sum _{j=0}^i\left\{\begin{array}{c}i\\ j\end{array}\right\}{g}_j?g_i=\sum _{j=0}^i(?1{)}^{i?j}\left[\begin{array}{c}i\\ j\end{array}\right]f_j$$

這題用到的是一個變式：
$$f_i=\sum _{j=0}^i\left\{\begin{array}{c}n?j\\ n?i\end{array}\right\}{g}_j?g_i=\sum _{j=0}^i(?1{)}^{i?j}\left[\begin{array}{c}n?j\\ n?i\end{array}\right]f_j$$
這個變式推一下就是題目里的那個了
證明：對于容斥原理&反演的思考和總結

代碼

算法一的TLE代碼，最大數據11s，正確性沒有問題

#include<cstdio> #include<cctype> #include<algorithm> #include<cstring> #define rg register typedef long long LL; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } int s,n,len; struct Graph {char s[101]; }G[61],nw,zc,Base[101]; int belo[11]; LL fac[11],ans; inline void add(Graph&a,const Graph&b) {for(rg int i=1;i<=len;i++)if(b.s[i]=='1')a.s[i]=a.s[i]=='0'?'1':'0'; } inline LL build() {int sum=0;for(rg int j=1;j<=s;j++){Graph self=G[j];for(rg int i=1;i<=len;i++)if(nw.s[i]=='1'&&self.s[i]=='1'){if(Base[i].s[i]==0){Base[i]=self,sum++;break;}else add(self,Base[i]);}}for(rg int i=1;i<=len;i++)if(nw.s[i]=='1')memset(Base[i].s,0,sizeof(Base[i].s));return 1ll<<(s-sum); } void dfs(const int step,const int maxnum) {if(step==n+1){int tot=0;for(rg int i=1;i<=n;i++)for(rg int j=i+1;j<=n;j++)if(belo[i]!=belo[j])nw.s[++tot]='1';else nw.s[++tot]='0';ans+=fac[maxnum-1]*build();return;}for(rg int i=1;i<=maxnum;i++)belo[step]=i,dfs(step+1,maxnum);belo[step]=maxnum+1,dfs(step+1,maxnum+1); } int main() {fac[0]=1;for(rg int i=1;i<=10;i++)fac[i]=-fac[i-1]*i;read(s);for(rg int i=1;i<=s;i++)scanf("%s",G[i].s+1);len=strlen(G[1].s+1);for(rg int i=1;i<=10;i++)if(i*(i-1)/2==len){n=i;break;}dfs(1,0);print(ans); return 0; }

貼上AC代碼

#include<cstdio> #include<cctype> #include<algorithm> #include<cstring> #define rg register typedef long long LL; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } int s,n,len; struct Graph {char s[101]; }G[61]; int belo[11]; LL Base[101],top,fac[11],ans; void dfs(const int step,const int maxnum) {if(step==n+1){int tot=0;top=0;for(rg int i=1;i<=n;i++)for(rg int j=i+1;j<=n;j++){tot++; if(belo[i]!=belo[j]){LL zt=0,each=1;for(rg int k=1;k<=s;k++,each<<=1)if(G[k].s[tot]=='1')zt|=each;for(rg int k=1;k<=top;k++)if((zt^Base[k])<zt)zt^=Base[k];if(zt)Base[++top]=zt;}}ans+=fac[maxnum-1]*(1ll<<(s-top));return;}for(rg int i=1;i<=maxnum;i++)belo[step]=i,dfs(step+1,maxnum);belo[step]=maxnum+1,dfs(step+1,maxnum+1); } int main() {fac[0]=1;for(rg int i=1;i<=10;i++)fac[i]=-fac[i-1]*i;read(s);for(rg int i=1;i<=s;i++)scanf("%s",G[i].s+1);len=strlen(G[1].s+1);for(rg int i=1;i<=10;i++)if(i*(i-1)/2==len){n=i;break;}dfs(1,0);print(ans); return 0; }

總結

這里這個線性基的技巧非常巧妙（甚至感覺這簡直是在考線性基的相關應用），然后斯特林反演其實也算是容斥了一波，只在推式子的過程中用到（但是不得不說這樣的模型不知為何用到的特別多），整道題還是非常清新的

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的斯特林反演[bzoj4671]异或图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。