【bzoj4671】异或图

Source

bzoj4671

Hint

请先思考后再展开

f(n)表示恰好n个联通块,g(n)表示至少n个联通块且g中统计系数为第二类斯特林数

Solution

请先思考后再展开

$g_k=\sum_{i=k}^n S2(i,k)f_i \leftrightarrow f_k=\sum_{i=k}^n S1(i,k)(-1)^{i-k}g_i$
$ans=\sum_{i=1}^n (-1)^{i-1}(i-1)!g_i$
因为是至少,会好算很多:枚举每一种分组情况(约120000个),那么相当于限制了一个mask是=0的
于是在mask意义下做线性基,贡献为 $2^{图数量-线性无关个数}$

时间复杂度 $120000*m*ln,3亿但跑不满$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
void chmax(int &x,const ll y) {x=(x>y?x:y);}
void chmin(int &x,const ll y) {x=(x<y?x:y);}
ll qread()
{
ll ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) putchar('-'),num=-num;
if(num>=10) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);putchar('\n');}
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
void add(ll &a,ll b){a+=b;if(a>=MOD)a-=MOD;if(a<=-MOD)a+=MOD;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll invm(ll x){return qpower(x,MOD-2);}
const int N=11,M=50;
int n,m,to[N][N];
typedef ll bs;bs bin[65],pp[65],fine;//bin曾经开小了
namespace lin
{
bs now[M];int qq;void clear(){memset(now,0,sizeof now);qq=0;}
void insert(bs num)
{
for(int i=0;i<M;i++) if(fine&bin[i] and num&bin[i])
{
if(now[i]!=0) num^=now[i];
else {qq++;now[i]=num;break;}
}
}
};
ll ans=0,fac[65];int blg[N];
void dfs(int now,int cnt)
{
if(now==n+1)
{
fine=0;for(int x=1;x<=n;x++) for(int y=x+1;y<=n;y++) if(blg[x]!=blg[y]) fine|=bin[to[x][y]];
lin::clear();for(int i=1;i<=m;i++) lin::insert(pp[i]);
ans+=((cnt&1)?1:-1)*fac[cnt-1]*bin[m-lin::qq];
return;
}
for(int i=1;i<=cnt+1;i++) blg[now]=i,dfs(now+1,cnt+(i==cnt+1));
}
char str[M];
void main()
{
bin[0]=1;for(int i=1;i<65;i++) bin[i]=bin[i-1]<<1;
fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i;
m=qread();
for(int t=1;t<=m;t++)
{
scanf("%s",str);int ss=strlen(str);n=1+sqrt(2*ss);
if(t==1) {int tmp=0;for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) to[i][j]=tmp,tmp++;}
for(int i=0;i<ss;i++) pp[t]|=bin[i]*(str[i]-'0');
}
dfs(1,0);write(ans);
}
};
int main()
{
freopen("a.in","r",stdin);
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/2956.html
转载请注明出处,谢谢!