bzoj4671: 异或图

Description

定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与

G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中.

现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异

或为一个连通图?

Input

第一行为一个整数s, 表图的个数.

接下来每一个二进制串, 第 i 行的二进制串为 gi, 其中 gi 是原图通过以下伪代码转化得

到的. 图的结点从 1 开始编号, 下面设结点数为 n.

Algorithm 1 Print a graph G = (V, E)

for i = 1 to n do

for j = i + 1 to n do

if G contains edge (i, j) then

print 1

else

print 0

end if

end for

end for

$ 2 ≤ n ≤ 10,1 ≤ s ≤ 60.$

Output

输出一行一个整数, 表示方案数

这道题刚看没什么思路。

\[f(i)=\sum_{j=i}^n g(j) * S(j,i)
\]

可以得到：

\[g(i)=\sum_{j=i}^n f(j) * s(j,i) * (-1)^{j-i}
\]

所以答案为

\[g(1)=\sum_{i=1}^n f(i) * s(i,1) * (-1)^{i-1}
\]

直接考虑这个式子容斥系数找规律也得到的结果相同。

我们知道$s(i,1) = (i-1)!$，阶乘和-1的幂次可以预处理，所以我们只要求出$f[i]$即可

我们用$Bell(n)$的复杂度枚举子集划分，把每个子集作为一个块，两个不同块之间不能连边，块内任意。

对于每一个图，用一个01向量表示两个不同块之间连每一条边的有无。

这样我们就转化为求有多少个子集异或为0

这个东西，我们求一下线性基，记线性基的元素个数为num

线性基里的向量是线性无关的，而其他的$2^{s-num}$个集合是一定可以通过异或线性基里的某些元素(或不异或)得到0的

所以答案即为$2^{s-num}$

但是这样直接做似乎会TLE，需要讲跨越块的边单独拿出来重新编号

还有一种方法，运用到一个性质：对于线性基的高斯消元，竖着消和横着消所得到的非0向量个数是相同的。

这个东西我不会证

#include<bits/stdc++.h>

using namespace std;

#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)

#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)

typedef long long ll;

inline int read(){

    int x;

    char c;

    int f=1;

    while((c=getchar())!='-' && (c<'0' || c>'9'));

    if(c=='-') c=getchar(),f=-1;

    x=c^'0';

    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');

    return x*f;

}

inline ll readll(){

    ll x;

    char c;

    ll f=1;

    while((c=getchar())!='-' && (c<'0' || c>'9'));

    if(c=='-') c=getchar(),f=-1;

    x=c^'0';

    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');

    return x*f;

}

const int maxm=60+1,maxn=10+1;

int n,m;

char s[maxm];

bool E[maxm][maxn][maxn];

int p[maxn],id[maxn][maxn];

ll a[maxm];

ll fac[maxm],ans;

struct point{

    int x,y;

}b[maxm];

void dfs(int x,int num){

    if(x>n){

        memset(a,0,sizeof(a));

        int res=0,tmp=-1;

        REP(i,1,n) REP(j,i+1,n) if(p[i]!=p[j]) b[++tmp]=(point){i,j};

        REP(i,1,m){

            ll nw=0;

            REP(j,0,tmp) if(E[i][b[j].x][b[j].y]) nw|=(1ll<<(ll)j);

            DREP(j,tmp,0)

                if(nw&(1ll<<(ll)j)){

                    if(a[j]) nw^=a[j];

                    else{

                        a[j]=nw;res++;

                        break;

                    }

                }

        }

/*      REP(i,1,n) REP(j,i+1,n){

            if(p[i]==p[j]) continue;

            ll nw=0;

            REP(k,1,m) if(E[k][i][j]) nw|=(1ll<<(ll)(k-1));

            DREP(k,m-1,0)

                if(nw&(1ll<<(ll)k)){

                    if(a[k]) nw^=a[k];

                    else{

                        a[k]=nw;res++;

                        break;

                    }

                }

        }

        */

        ans+=fac[num-1]*(1ll<<(ll)(m-res));

        return;

    }

    REP(i,1,num+1) p[x]=i,dfs(x+1,max(num,i));

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("cnt.in","r",stdin);

    freopen("cnt.out","w",stdout);

#endif

    m=read();

    scanf("%s",s+1);int len=strlen(s+1);

    while(n*(n-1)/2<len) ++n;len=0;

    REP(i,1,n)

        REP(j,i+1,n)

            E[1][i][j]=s[id[i][j]=++len]-'0';

    REP(k,2,m){

        len=0;scanf("%s",s+1);

        REP(i,1,n) REP(j,i+1,n)  E[k][i][j]=s[++len]-'0';

    }

    fac[0]=1;

    REP(i,1,n) fac[i]=-fac[i-1]*i;

    dfs(1,0);

    printf("%lld\n",ans);

    return 0;

}

巴特西

bzoj4671: 异或图

bzoj4671: 异或图

Description

Input

Output

最新文章

热门文章