题目大意

给出一个 \(n\) 个点的图，每个点都有一个权值 \(f_i\) ，如果 \(f_i=-1\) 表示 \(i\) 这个点是坏的。定义一个点是有用的当且仅当它不是坏的，并且它连的点中至少有一个点不是坏的。问有多少种生成树满足有用的点的权值之和 \(\le \lim\)。

\(n\le 40\)

思路

其实这道题目不难，只是脑子卡路了而已。。。

可以想到，我们可以先统计选出哪些点为有用点权值 \(\le lim\)，我们记录有 \(i\) 个有用点且合法的方案数为 \(\text{sum}(i)\)，你发现统计有多少种生成树满足有 \(i\) 个有用点其实只跟 \(i\) 有关，这个可以用矩阵树定理求出来，两者相乘就是有 \(i\) 个有用点时产生的贡献。

具体讲一下吧，前面那个东西可以折半搜索，就是拆成两部分然后合起来考虑，排个序就好了。时间复杂度 \(\Theta(n2^{n/2})\) 。

后面一个关键就在于容斥，你发现其实恰好有 \(i\) 个有用点不是很好求，但是至多有 \(i\) 个有用点其实比较好求，具体来说，连边的方法就是不坏但不有用的点只能连坏点，坏点可以随便连，然后求生成树个数。考虑至多有 \(i\) 个有用点的方案数为 \(F(i)\)，恰好有 \(i\) 个有用点的方案数为 \(G(i)\)，那么可以得到关系式：

\[G(i)=F(i)-\sum_{j=0}^{i-1}\binom{i}{j}G(j)
\]

正确性显然。此部分时间复杂度瓶颈为矩阵树定理部分，所以为 \(\Theta(n^3)\) 。

\(\texttt{Code}\)

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define mod 1000000007

#define MAXM 1050005

#define MAXN 55

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,lim,tot,cnt1,cnt2,cc[MAXN],bin[MAXN][MAXN],Cnt[MAXN],Sum[MAXN],val[MAXN]; 

int mul (int a,int b){return 1ll * a * b % mod;}

int dec (int a,int b){return a >= b ? a - b : a + mod - b;}

int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}

int qkpow (int a,int b){int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);return res;}

int inv (int x){return qkpow (x,mod - 2);}

struct node{

	int s,d;

	bool operator < (const node &p)const{return s < p.s;}

}c1[MAXM],c2[MAXM];

void dfs1 (int x,int S,int D){

	if (S > lim) return ;

	if (x > m) return c1[++ cnt1] = node {S,D},void ();

	dfs1 (x + 1,S,D);

	if (val[x] != -1) dfs1 (x + 1,S + val[x],D + 1);

}

void dfs2 (int x,int S,int D){

	if (S > lim) return ;

	if (x > n) return c2[++ cnt2] = node {S,D},void ();

	dfs2 (x + 1,S,D);

	if (val[x] != -1) dfs2 (x + 1,S + val[x],D + 1);

}

int mat[MAXN][MAXN];

void Link (int x,int y){mat[x][x] ++,mat[y][y] ++,mat[x][y] --,mat[y][x] --;}

int MatrixTree (int k){//至多k个有用点的方案书

	for (Int i = 1;i <= n;++ i) for (Int j = 1;j <= n;++ j) mat[i][j] = 0;

	for (Int i = 1;i <= n;++ i)

		for (Int j = i + 1;j <= n;++ j)

			if (i <= k){if (j <= k || j > tot) Link (i,j);}

			else if (i > tot) Link (i,j);

			else if (j > tot) Link (i,j);

	for (Int i = 1;i <= n;++ i) for (Int j = 1;j <= n;++ j) mat[i][j] = (mat[i][j] % mod + mod) % mod;

	int res = 1;

	for (Int i = 1;i < n;++ i){

		for (Int j = i + 1;j < n;++ j){

			int t = mul (mat[j][i],inv (mat[i][i]));

			for (Int k = i;k < n;++ k) mat[j][k] = dec (mat[j][k],mul (t,mat[i][k]));

		}

		res = mul (res,mat[i][i]);

	}

	return res;

}

signed main(){

	read (n,lim),m = (n + 1) / 2;

	for (Int i = 1;i <= n;++ i) read (val[i]),tot += (val[i] != -1);

	dfs1 (1,0,0),dfs2 (m + 1,0,0);

	sort (c1 + 1,c1 + cnt1 + 1);

	sort (c2 + 1,c2 + cnt2 + 1);

	for (Int i = cnt1,j = 1;i;-- i){

		while (j <= cnt2 && c1[i].s + c2[j].s <= lim) cc[c2[j].d] ++,j ++;

		for (Int k = 0;k <= n;++ k) Cnt[c1[i].d + k] = add (Cnt[c1[i].d + k],cc[k]);

	}

	for (Int i = 0;i <= n;++ i) bin[i][0] = 1;

	for (Int i = 1;i <= n;++ i)

		for (Int j = 1;j <= i;++ j)

			bin[i][j] = add (bin[i - 1][j - 1],bin[i - 1][j]);

	for (Int i = 0;i <= tot;++ i) Sum[i] = MatrixTree (i);

	for (Int i = 1;i <= tot;++ i)

		for (Int j = 0;j < i;++ j)

			Sum[i] = dec (Sum[i],mul (bin[i][j],Sum[j]));

	int res = 0;for (Int i = 0;i <= tot;++ i) res = add (res,mul (Cnt[i],Sum[i]));

	write (res),putchar ('\n');

	return 0;

}

巴特西

题解「2017 山东一轮集训 Day5」苹果树

题目大意

思路

\(\texttt{Code}\)

最新文章

热门文章

巴特西

题解 「2017 山东一轮集训 Day5」苹果树

题目大意

思路

\(\texttt{Code}\)

最新文章

热门文章

题解「2017 山东一轮集训 Day5」苹果树