题目
点这里看题目。
分析
看到 n 很小，限制条件又这么复杂，显然可以直接容斥。
我们实际上只需要保证每个公司都有边可以修建（树的性质保证最终每个公司有且仅有一条边可以修建）。因此不难有容斥：
[egin{aligned}
f(k):& ext{有}k ext{个公司没有边修建的方案数}\
ans=&sum_{i=0}^{n-1}(-1)^if(i)
end{aligned}
]
而所有的(f)都可以一遍枚举子集计算。时间复杂度(O(2^nn^3))。看着慢，跑着还不错。
代码
#include <cstdio>
#include <iostream>
const int mod = 1e9 + 7;
const int MAXN = 25, MAXM = 17 * 17, MAXS = ( 1 << 17 ) + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
int D[MAXN][MAXN], K[MAXN][MAXN], G[MAXN][MAXN];
int M[MAXN], fr[MAXN][MAXM], to[MAXN][MAXM];
int N;
int qkpow( int base, int indx )
{
int ret = 1;
while( indx )
{
if( indx & 1 ) ret = 1ll * ret * base % mod;
base = 1ll * base * base % mod, indx >>= 1;
}
return ret;
}
int inv( const int a ) { return qkpow( a, mod - 2 ); }
int det( int T[MAXN][MAXN], const int n )
{
int indx, ret = 1, tmp, inver;
for( int i = 1 ; i <= n ; i ++ )
{
indx = -1;
for( int j = i ; j <= n ; j ++ )
if( T[j][i] )
{ indx = j; break; }
if( indx == -1 ) return 0;
if( indx ^ i ) ret = mod - ret;
std :: swap( T[i], T[indx] );
inver = inv( T[i][i] );
for( int j = i + 1 ; j <= n ; j ++ )
if( T[j][i] )
{
tmp = 1ll * T[j][i] * inver % mod;
for( int k = i ; k <= n ; k ++ )
T[j][k] = ( T[j][k] - 1ll * T[i][k] * tmp % mod + mod ) % mod;
}
ret = 1ll * ret * T[i][i] % mod;
}
return ret;
}
int MatrixTree()
{
for( int i = 1 ; i <= N ; i ++ )
{
D[i][i] = 0;
for( int j = 1 ; j <= N ; j ++ )
D[i][i] += G[j][i];
}
for( int i = 1 ; i <= N ; i ++ )
for( int j = 1 ; j <= N ; j ++ )
K[i][j] = ( D[i][j] - G[i][j] + mod ) % mod;
return det( K, N - 1 );
}
int main()
{
read( N );
for( int i = 1 ; i < N ; i ++ )
{
read( M[i] );
for( int j = 1 ; j <= M[i] ; j ++ )
read( fr[i][j] ), read( to[i][j] ),
G[fr[i][j]][to[i][j]] ++, G[to[i][j]][fr[i][j]] ++;
}
int upper = 1 << N - 1, coe, ans = 0;
for( int S = 0 ; S < upper ; S ++ )
{
coe = 1;
for( int i = 1 ; i < N ; i ++ )
if( S & ( 1 << i - 1 ) )
{
for( int j = 1 ; j <= M[i] ; j ++ )
G[fr[i][j]][to[i][j]] --, G[to[i][j]][fr[i][j]] --;
coe = mod - coe;
}
ans = ( ans + 1ll * coe * MatrixTree() % mod ) % mod;
for( int i = 1 ; i < N ; i ++ )
if( S & ( 1 << i - 1 ) )
for( int j = 1 ; j <= M[i] ; j ++ )
G[fr[i][j]][to[i][j]] ++, G[to[i][j]][fr[i][j]] ++;
}
write( ans ), putchar( '
' );
return 0;
}