文章目录
题目思路另解代码
题目
Luogu
n
n
n 个点，修成一棵树，
n
−
1
n-1
n−1 个公司，每个公司能修一些边，但只能修一条，求方案数
思路
由于是树，所以条件转化(最重要的一步)： [每个公司修一条边]=[每个公司修边]=[
a
1
a_1
a1 修
∩
\cap
∩
a
2
a_2
a2 修
∩
\cap
∩ …
∩
\cap
∩
a
n
a_n
an 修] 于是
2
n
2^n
2n 枚举公司然后矩阵树即可 时间复杂度
O
(
2
n
∗
n
3
)
O(2^n*n^3)
O(2n∗n3)
另解
自己瞎想的 矩阵树每个点看成一个
2
n
−
1
2^{n-1}
2n−1 项的多项式,每一项为
k
∗
a
t
1
a
t
2
.
.
.
a
t
m
k*a_{t_1}a_{t_2}...a_{t_m}
k∗at1at2...atm 开始时形如
−
a
t
1
−
a
t
2
−
.
.
.
-a_{t_1}-a_{t_2}-...
−at1−at2−... 或者
a
t
1
+
a
t
2
.
.
.
a_{t_1}+a_{t_2}...
at1+at2... 之类的 好像不能消元…咕了
O
(
2
n
∗
n
3
)
O(2^n*n^3)
O(2n∗n3)
代码
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std
;
#define LL long long
#define ULL unsigned long long
int read(){
int f
=1,x
=0;char c
=getchar();
while(c
<'0'||'9'<c
){if(c
=='-')f
=-1;c
=getchar();}
while('0'<=c
&&c
<='9'){x
=x
*10+c
-'0';c
=getchar();}
return f
*x
;
}
#define MAXN 300
#define INF 0x3f3f3f3f
#define Mod (int)(1e9+7)
LL mat
[MAXN
+5][MAXN
+5],a
[MAXN
+5][MAXN
+5];
LL
Pow(LL x
,int y
){
LL ret
=1;
while(y
){
if(y
&1) ret
=ret
*x
%Mod
;
x
=x
*x
%Mod
,y
>>=1;
}
return ret
;
}
int Det(int n
){
n
--;
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
mat
[i
][j
]=(a
[i
][j
]+Mod
)%Mod
;
for(int i
=1;i
<=n
;i
++){
for(int j
=i
+1;j
<=n
;j
++)
if(!mat
[i
][i
]&&mat
[j
][i
]){
swap(mat
[i
],mat
[j
]);
break;
}
LL Inv
=Pow(mat
[i
][i
],Mod
-2);
for(int j
=i
+1;j
<=n
;j
++){
LL tmp
=mat
[j
][i
]*Inv
%Mod
;
for(int k
=i
;k
<=n
;k
++)
mat
[j
][k
]=(mat
[j
][k
]-tmp
*mat
[i
][k
]%Mod
+Mod
)%Mod
;
}
}
LL ret
=1;
for(int i
=1;i
<=n
;i
++)
ret
=ret
*mat
[i
][i
]%Mod
;
return ret
;
}
int n
;
LL ans
;
vector
<pair
<int,int> > Edge
[MAXN
+5];
void DFS(int d
,int k
){
if(d
==n
){
ans
=(ans
+Mod
+k
*Det(n
))%Mod
;
return ;
}
DFS(d
+1,-k
);
for(int i
=0;i
<(int)Edge
[d
].size();i
++){
int u
=Edge
[d
][i
].first
,v
=Edge
[d
][i
].second
;
a
[u
][u
]++,a
[v
][v
]++,a
[u
][v
]--,a
[v
][u
]--;
}
DFS(d
+1,k
);
for(int i
=0;i
<(int)Edge
[d
].size();i
++){
int u
=Edge
[d
][i
].first
,v
=Edge
[d
][i
].second
;
a
[u
][u
]--,a
[v
][v
]--,a
[u
][v
]++,a
[v
][u
]++;
}
return ;
}
int main(){
n
=read();
for(int i
=1;i
<n
;i
++){
int m
=read();
for(int j
=1;j
<=m
;j
++)
Edge
[i
].push_back(make_pair(read(),read()));
}
DFS(1,1);
printf("%lld\n",ans
);
return 0;
}
