【BZOJ】4671: 异或图

题解

写完之后开始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 <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <map>

//#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 register

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

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<class T>

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;

}

巴特西

【BZOJ】4671: 异或图

题解

代码

最新文章

热门文章