「康复训练」6月15日联考

发表于

NOI2018 前的联考第二场。

深邃

Description

当我们伟大的领袖 V 还小的时候，他的目光就十分深邃，显示出他过人的天赋。这一天，他将目光投向了贤者之森里的一棵树。

这是一棵有 nn 个节点 n−1n-1 条边的树，其中有 kk 个节点长有果实，V 想删去一些边，使得树分为几个连通块，满足每个连通块都包含至少一个果实，并且最大的连通块最小。V 请你求出答案，thank you sir!

Constraints

$ n \leq 200000$

Solution

根据题意很容易想到二分，二分答案后在树上贪心地取。 f(x,0)f(x,0) 表示在 xx 这个点的子树里的点与 xx 构成连通块且不包含特殊点的连通块大小， f(x,1)f(x,1) 表示包含特殊点的连通块大小，贪心地尽量能包含就包含即可。

Code

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
const int inf=0x3f3f3f3f;
int n,k,cnt,x,y,ans,mx;
int first[N],f[N][2];
bool ok,good[N];
struct edge{int to,next;}e[N*2];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void Min(int& a,int b){if(b<a)a=b;}
void Max(int& a,int b){if(b>a)a=b;}
void dfs(int x,int fa)
{
	if(good[x])f[x][0]=0;
	int sum=0,mn=good[x]?0:inf;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa)continue;
		dfs(to,x);sum+=f[to][0];
		Min(mn,f[to][1]);
	}
	if(sum+mn+1<=mx)f[x][1]=sum+mn+1,f[x][0]=0;
	else if(sum+1<=mx&&x!=1)f[x][0]=sum+1;
	else ok=false;
}
bool check(int x)
{
	mx=x;ok=true;
	memset(f,0x3f,sizeof(f));
	dfs(1,-1);return ok;
}
int main()
{
	n=read();k=read();
	for(int i=1;i<n;i++)
	{
		x=read();y=read();
		ins(x,y);ins(y,x);
	}
	for(int i=1;i<=k;i++)
		x=read(),good[x]=true;
	int L=1,R=n,mid;
	while(L<=R)
	{
		mid=(L+R)>>1;
		if(check(mid))ans=mid,R=mid-1;
		else L=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}

黑暗

Description

我们伟大的领袖 V 吃掉了树上的果实，得到了黑暗的力量，战无不胜。当 V 又一次获得了胜利的时候，他开始思考自己为什么会被赋予这样的天赋，决定拜访一些著名的哲学家寻找答案。

新日暮里一共有 nn 个哲学家，任意两个哲学家之间都有可能有通讯，一个哲学家联盟指的是一个极大的哲学家集合，使得任意两名哲学家都可以直接或者间接地通讯。我们称新日暮里的哲学程度为哲学家联盟的个数的 mm 次方， V 想知道对于通讯情况的哲学程度的和。

简化版题意：nn 个点的无向图，每条边都可能存在，一个图的权值是连通块个数的 mm 次方，求所有可能的图的权值和。

答案对 998244353998244353 取模。

Constraints

T≤1000T \leq 1000 ， n≤30000n \leq 30000 ， m≤15m \leq 15

Solution

令 f(i,j)f(i,j) 表示 ii 个点构成了 jj 个连通块的方案数。则对于 j≤2j\leq 2 的情况，通过枚举 11 所在的连通块大小可得到式子：

f(i,j)=∑k=1i−1f(i−k,j−1)f(k,1)(i−1k−1)f(i,j)=\sum_{k=1}^{i-1}f(i-k,j-1)f(k,1)\binom{i-1}{k-1}

而对于 j=1j=1 的情况，通过容斥可以得到：

f(i,1)=2i(i−1)2−∑k=2if(i,k)f(i,1)=2^{\frac{i(i-1)}{2}}-\sum_{k=2}^{i}f(i,k)

期望得分 40 分。

若令 f(i,j)f(i,j) 表示 ii 个点，权值为连通块个数的 jj 次方的总和，则由式子 (n+1)m=∑i=0m(mi)ni(n+1)^m=\sum_{i=0}^{m}\binom{m}{i}n^i 可以推出：

f(i,j)=∑k=1ig(k)(i−1k−1)∑t=0j(jt)f(i−k,t)f(i,j)=\sum_{k=1}^{i}g(k)\binom{i-1}{k-1}\sum_{t=0}^{j}\binom{j}{t}f(i-k,t)

其中 g(k)g(k) 为 kk 个点的连通图方案数，令 h(i)=2i(i−1)2h(i)=2^{\frac{i(i-1)}{2}} ，则可以用以下式子得到：

g(i)=h(i)−∑j=1i−1g(j)h(i−j)(i−1j−1)g(i)=h(i)-\sum_{j=1}^{i-1}g(j)h(i-j)\binom{i-1}{j-1}

可以预处理枚举 tt 的部分，期望得分 60 分。

Code

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<vector>
#define LL long long
using namespace std;
const int N=505;
const int mod=998244353;
int T,n,m,ans;
int bit[N*N],a[N][16],f[N][N],C[N][N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void Mod(int& a,int b){a+=b;if(a>=mod)a-=mod;}
int main()
{
	bit[0]=1;
	for(int i=1;i<=250000;i++)
		bit[i]=bit[i-1]*2%mod;
	for(int i=0;i<=500;i++)C[i][0]=1;
	for(int i=1;i<=500;i++)
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	f[1][1]=1;
	for(int x=2;x<=500;x++)
	{
		for(int i=2;i<=x;i++)
			for(int j=i-1;j<x;j++)
				Mod(f[x][i],1ll*f[j][i-1]*f[x-j][1]%mod*C[x-1][j]%mod);
		int sum=0;
		for(int i=2;i<=x;i++)Mod(sum,f[x][i]);
		f[x][1]=(bit[x*(x-1)/2]-sum+mod)%mod;
	}
	for(int i=1;i<=500;i++)a[i][0]=1;
	for(int i=1;i<=500;i++)
		for(int j=1;j<=15;j++)
			a[i][j]=1ll*a[i][j-1]*i%mod;
	T=read();
	while(T--)
	{
		n=read();m=read();ans=0;
		for(int i=1;i<=n;i++)
			Mod(ans,1ll*f[n][i]*a[i][m]%mod);
		printf("%d\n",ans);
	}
	return 0;
}