【BZOJ】4671: 异或图-白红宇

【BZOJ】4671: 异或图

阅读量：4617 次

发布时间：2019-06-09

本文共 2561 字，大约阅读时间需要 8 分钟。

题解

写完之后开始TTTTTTT……懵逼

这道题我们考虑一个东西叫容斥系数啊><

这个是什么东西呢

也就是\(\sum_{i = 1}^{m}\binom{m}{i}f_{i} = [m = 1]\)

也就是说，我们求出m个系数，让这个式子只在[m = 1]的时候为1，其余时候为0

~~啥玩意啊怎么求啊~~

我们显然可以

\(n^2\)的递推求出来，类似解方程

但是我们打个表就会发现是\(f_{i} = (-1)^{i - 1}(i - 1)!\)

然后我们再考虑这个式子的容斥意义，假如一个图有m个联通块，那么我们会计算有i个联通块的图(i <= m)的时候，都会把这个图算\(\binom{m}{i}\)遍，我们只要乘上容斥系数，就可以保证我们如果这个图是一个联通块的话值是1，否则是0

好的，那么我们考虑如何计算这个子问题至少有m个联通块的图有多少个

我们dfs每个点构成了不同集合的方案，如果一个点在同一集合，连边任意，不在同一集合的一定没有边

这样的话，我们把不在同一集合的一个点对(i,j)作为二进制的数位，如果某张图有(i,j)这条边，那么值为1，否则值为0

那么我们就是变成了要求，有s个数，异或起来为0的方案数

这个可以线性基，答案是\(2^{s - 线性基个数}\)

线性基求的方法有点鬼畜，但是正常的求线性基会T（猫锟是怎么卡的常数啊QAQ

我们把线性无关组存起来，每次得到一个新值和前面的所有值异或一下，如果异或后的值会变小就异或

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          //#define ivorysi#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define mp make_pair#define pb push_back#define fi first#define se second#define mo 974711#define MAXN 3005#define RG registerusing namespace std;typedef long long int64;typedef double db;template
           
            void read(T &res) { res = 0;char c = getchar();T f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f;}template
            
             void out(T x) { if(x < 0) {putchar('-');x = -x;} if(x >= 10) { out(x / 10); } putchar('0' + x % 10);}int64 fac[15],b[65],ans;int S,graph[65][15][15],N,id[15],L;char str[105];void dfs(int u,int x) { if(u > N) { memset(b,0,sizeof(b)); int t = 0; for(int k = 1 ; k <= S ; ++k) { int64 val = 0; int p = 0; for(int i = 1 ; i <= N ; ++i) { for(int j = i + 1 ; j <= N ; ++j) { if(id[i] != id[j]) { val |= (1LL << p) * graph[k][i][j];++p; } } } for(int i = 1 ; i <= t ; ++i) { if((val ^ b[i]) < val) val ^= b[i]; } if(val) b[++t] = val; } ans += fac[x] * (1LL << (S - t)); return; } for(int i = 1 ; i <= x + 1 ; ++i) { id[u] = i;dfs(u + 1,x + (i > x)); }}void Solve() { scanf("%d",&S); scanf("%s",str + 1); N = strlen(str + 1); for(int i = 1 ; i <= 10 ; ++i) { if(i * (i - 1) / 2 == N) { N = i; break; } } for(int k = 1 ; k <= S ; ++k) { int p = 0; for(int i = 1 ; i <= N; ++i) { for(int j = i + 1 ; j <= N ; ++j) { graph[k][i][j] = str[++p] - '0'; } } if(k != S) scanf("%s",str + 1); } fac[1] = 1; for(int i = 2 ; i <= N ; ++i) fac[i] = fac[i - 1] * (1 - i); L = N * (N - 1) / 2; dfs(1,0); out(ans);putchar('\n'); //out(clock() / 1000000);}int main() {#ifdef ivorysi freopen("f1.in","r",stdin);#endif Solve(); return 0;}

转载于:https://www.cnblogs.com/ivorysi/p/9109307.html

你可能感兴趣的文章