注意
线性基空间要开够，1左移超过31位应该写成1LL
前置芝士
斯特林反演
斯特林反演有两种形式（和二项式反演类似）
\[ G_n=\sum_{i=1}^n\left\{\begin{matrix}n\\i\end{matrix}\right\}F_i\Rightarrow F_n=\sum_{i=1}^n(-1)^{n-i}\left[\begin{matrix}n\\i\end{matrix}\right]G_i \]
\[ G_k=\sum_{i=k}^n\left\{\begin{matrix}i\\k\end{matrix}\right\}F_i\Rightarrow F_k = \sum_{i=k}^n(-1)^{i-k}\left[\begin{matrix}i\\k\end{matrix}\right]G_i \]
思路
利用第一种形式
设\(g_i\)表示至少有i个连通块，用\(f_i\)表示恰好有i个联通块的方案数
首先\(ans=\sum_{i=1}^n T_i F_i\)，先胡乱写一个式子，然后考虑\(T_i\)这个容斥系数到底是什么东西 每项被计算的次数是\(\left\{\begin{matrix}n\\i\end{matrix}\right\}\) 因为最后的答案中应该只包含1个连通块的贡献，所以可以得到一个式子\[ \sum_{i=1}^n\left\{\begin{matrix}n\\i\end{matrix}\right\}T_i=\left[n=1\right] \] 斯特林反演一下有\[ \sum_{i=1}^n\left[\begin{matrix}n\\i\end{matrix}\right][n=1]=T_n \] 所以\[ T_i=(-1)^{n-i}(n-i)! \]利用第二种形式
容易发现直接求并不好求，考虑反演一发
对于集合划分问题，一般都使用斯特林反演 设\(g_i\)表示至少有i个连通块，用\(f_i\)表示恰好有i个联通块的方案数 对于\(g_i\)我们可以枚举一个子集的划分，不在同一个子集中的点之间一定没有边，在同一个子集中的点之间可以随意连边，这样就保证了如果划分了i个集合，那么最少会有i个连通块 接下来考虑系数，假设当前恰好划分出i个连通块，为了满足\(g_k\)的条件，相当于要把这i个连通块划分到k个新的连通块中，所以每个\(f_i\)会产生\(\left\{\begin{matrix}i\\k\end{matrix}\right\}\)的贡献 所以能够得到\(f_i\)和\(g_i\)的关系\[ g_k=\sum_{i=k}^n \left\{\begin{matrix}i\\k\end{matrix}\right\}f_i \] 根据斯特林反演公式 得到\[ f_k=\sum_{i=k}^n(-1)^{i-k}\left[\begin{matrix}i\\k\end{matrix}\right]g_i \] 因为要求\(f_1\) 所以得到\[ \begin{align}f_1&=\sum_{i=1}^n(-1)^{i-1}\left[\begin{matrix}i\\1\end{matrix}\right]g_i\\&=\sum_{i=1}^n(-1)^{i-1}(i-1)!g_i\end{align} \]利用反演得出的柿子求解
第一种和第二种得出的式子是相同的，考虑如何计算\(G_i\)
dfs计算划分之后，把每个数都当成一个二进制数，确定每个图上没有那些边相连后，将其插入线性基中，最后求异或和为0的方案数，求异或和为零的方案数相当于要找到线性无关的组的个数，剩下的可以随便取，所以\(g_i=2^{n-t}\)t是线性无关的个数代码
#include#include #include #define int long longusing namespace std;int n,T,has[100][20][20],belong[20],jd[100],nob,jc[40],ans=0;char s[200];void init(void){ nob=0; memset(jd,0,sizeof(jd));}void insert(int s){ for(int i=62;i>=1;i--){ if((s>>(i-1))&1LL){ if(!jd[i]){ nob++; jd[i]=s; break; } else s^=jd[i]; } }}void init_jc(void){ jc[0]=1; for(int i=1;i<=20;i++) jc[i]=(jc[i-1]*i);}void dfs(int num,int id){ // printf("%lld %lld\n",num,id); if(num==n){ init(); for(int i=1;i<=T;i++){ int S=0,mid=0; for(int j=1;j<=n;j++) for(int k=j+1;k<=n;k++){ mid++; if(belong[j]!=belong[k]){ S|=(1LL<<(mid-1))*has[i][j][k]; } } insert(S); } ans+=(((id-1)&1)?-1:1)*(jc[id-1])*(1LL<<(T-nob)); return; } for(int i=1;i<=id;i++){ belong[num+1]=i; dfs(num+1,id); belong[num+1]=0; } belong[num+1]=id+1; dfs(num+1,id+1); belong[num+1]=0;}signed main(){ init_jc(); scanf("%lld",&T); for(int i=1;i<=T;i++){ scanf("%s",s+1); int l=strlen(s+1); // printf("l=%d\n",l); if(!n) for(int j=1;;j++) if(j*(j-1)==2*l){ n=j; break; } int mid=1; for(int j=1;j<=n;j++) for(int k=j+1;k<=n;k++) has[i][j][k]=has[i][k][j]=s[mid++]-'0'; } dfs(0,0); printf("%lld\n",ans); return 0;}