bzoj4671: 异或图——斯特林反演

[BZOJ4671]异或图 - xjr01 - 博客园

考虑先算一些限制少的情况

gi表示把n个点的图，划分成i个连通块的方案数

连通块之间不连通很好处理（怎么处理看下边），但是内部必须连通，就很难办了

所以再降低条件，fi表示，把n个点的图，划分成i个"连通块"，保证连通块之间不会有边相连，但是内部可以不连通的方案数

fi计算方法如下：

用Bell(n)的复杂度枚举集合划分，然后相邻集合之间不能连边，

然后考虑凑出符合这个集合划分的图有多少个，异或高斯消元，xi表示第i个图选择与否，如果必须不选，等号右边就是0，否则不管。

求自由元个数

fi和gi的关系：

就是枚举到底是有几个连通块

然后斯特林反演：

虽然往上枚举，但是式子证明思路是一样的，(-1)项的指数只要保证在所谓[n=m]时候是偶数就好了

高斯消元也可以换成线性基

每个图一个元素。每个线性基的位表示这个图这个边有没有，并且再和这次必要的边取&

要求多少个子集xor为全0

线性基之后，2^(s-sz）即可。

代码：

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

#define int long long

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int M=;

const int N=;

int n,m;

int edge[M][][];

ll f[*];

ll t[N];

int ans[M];

char s[N*N];

ll id[N];

int vis[*];

ll Guass(int n){

    memset(ans,-,sizeof ans);

    memset(vis,,sizeof vis);

//    for(reg i=1;i<=n;++i){

//        for(reg j=1;j<=m;++j){

//            cout<<f[i][j]<<" ";

//        }cout<<" = "<<f[i][m+1]<<endl;

//    }

//    cout<<endl;

    int free=;

    for(reg i=;i<=m;++i){

        int id=;

        for(reg j=;j<=n;++j){

            if((!vis[j])&&(f[j]&(1LL*<<(i-)))) id=j;

        }

        if(!id){

            ++free;continue;

        }

        vis[i]=;

        if(id!=i) swap(f[i],f[id]);

        for(reg j=;j<=n;++j){

            if(j==i) continue;

            if(!vis[j]&&(f[j]&(1LL*<<(i-)))){

                f[j]^=f[i];

            }

        }

    }

    return (1LL*<<free);

}

void dfs(int x,int sz){

    if(x==n+){

        //cout<<" x "<<x<<" sz "<<sz<<endl;

        memset(f,,sizeof f);

        int cnt=;

        for(reg i=;i<=n;++i){

            for(reg j=i+;j<=n;++j){

                if(id[i]!=id[j]){

                    ++cnt;

                    for(reg k=;k<=m;++k){

                        if(edge[k][i][j]) f[cnt]|=(1LL*<<(k-));

                    }

                }

            }

        }

    //    cout<<" cnt "<<cnt<<endl;

        t[sz]+=Guass(max(cnt,m));

        return;

    }

    for(reg i=;i<=sz;++i){

        id[x]=i;

        dfs(x+,sz);

        id[x]=;

    }

    id[x]=sz+;

    dfs(x+,sz+);

    id[x]=;

}

void calc(int l){

    for(n=;n<=;++n){

        if(n*(n-)/==l) break;

    }

}

int main(){

    rd(m);

    for(reg i=;i<=m;++i){

        scanf("%s",s+);

        int l=strlen(s+);

        if(!n) calc(l);

        int t=;

        for(reg j=;j<=n;++j){

            for(reg k=j+;k<=n;++k){

                ++t;

                edge[i][j][k]=edge[i][k][j]=s[t]-'';

            }

        }

    }

    dfs(,);

    ll ans=,jie=;

    for(reg i=;i<=n;++i){

        if(i&){

        ans+=jie*t[i];

        }else{

        ans-=jie*t[i];

        }

        jie*=i;

    }

    printf("%lld",ans);

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

Author: *Miracle*

Date: 2019/2/16 21:40:44

*/

总结：

找到两个数组f，g

f范围宽松好统计，g范围严格难统计但是和答案有直接关系，

这样，只要得到f和g的关系，就可以找到答案！

异或下线性方程组的自由元个数：

先变成n*(n+1)的矩阵

然后高斯消元，如果某一个id找不到，那么一定是自由元了，计数器++

注意，每次找i和消除必须在全局位置，并且用一个vis标记表示是否还能动

最后削成的上三角矩阵，除了无解情况，剩下的一定有唯一解

巴特西

bzoj4671: 异或图——斯特林反演

[BZOJ4671]异或图 - xjr01 - 博客园

最新文章

热门文章