QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423207#990. Colorful ComponentsOvO_ZuoAC ✓158ms4868kbC++142.4kb2024-05-27 21:32:482024-05-27 21:32:50

Judging History

你现在查看的是最新测评结果

  • [2024-05-27 21:32:50]
  • 评测
  • 测评结果:AC
  • 用时:158ms
  • 内存:4868kb
  • [2024-05-27 21:32:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=305,mo=1e9+7;

int add(int x,int y){ x+=y;return x>=mo?x-mo:x;}
int mi(int x,int y) {
	y=(y+mo-1)%(mo-1);
	int res=1;
	for(;y;y>>=1,x=(ll)x*x%mo)
		if(y&1) res=(ll)res*x%mo;
	return res;
}

int frac[N],inv[N];
void init() {
	frac[0]=1;
	for(int i=1;i<N;i++) frac[i]=(ll)frac[i-1]*i%mo;
	inv[N-1]=mi(frac[N-1],mo-2);
	for(int i=N-2;i>=0;--i) inv[i]=(ll)inv[i+1]*(i+1)%mo;
}	
int C(int x,int y) {
	if(x<y) return 0;
	return (ll)frac[x]*inv[y]%mo*inv[x-y]%mo;
}

int n,m;
int cnt[N];
int pv[N];
int f[N][N];// i 个点分成 j 个合法连通块的答案
int sum[N];// 由合法连通块构成的大小为 i 的块的答案
int g[N][N];// i 个点分成 j 个连通块的答案
int h[N][N];// 考虑完前 i 种颜色选出了 j 个连通块的答案
int main()
{
	init();
	scanf("%d%d",&n,&m);
	int i,j,k,p;
	for(i=1;i<=n;i++) scanf("%d",&j),cnt[j]++;
	for(i=1;i<=n;i++) pv[i]=mi(i,i-2);
	int tv;
	
	f[0][0]=1;
	for(i=1;i<=n;i++)	
		for(j=1;j<=n;j++) 
			for(k=1;k<=i&&k<=m;k++) 
				f[i][j]=add(f[i][j],
					(ll)f[i-k][j-1]*
						C(i-1,k-1)%mo*
						pv[k]%mo*k%mo);
						
	for(i=1;i<=n;i++) {
		for(j=1;j<=i;j++) {
			tv=(ll)f[i][j]*mi(i,j-2)%mo;
			if(j&1) sum[i]=add(sum[i],tv);
			else sum[i]=add(sum[i],mo-tv);
		}
		sum[i]=(ll)sum[i]*i%mo;
	}
	
	g[0][0]=1;
	for(i=1;i<=n;i++) 
		for(j=1;j<=i;j++)
			for(k=1;k<=i;k++) 
				g[i][j]=add(g[i][j],
					(ll)g[i-k][j-1]*
						sum[k]%mo*C(i-1,k-1)%mo);

	int lst=0;
	h[0][0]=1;
	for(i=1;i<=n;i++) {
		if(!cnt[i]) continue;
		for(j=0;j<n;j++) 
			for(k=1;k<=cnt[i]&&j+k<=n;k++) 
				h[i][j+k]=add(h[i][j+k],
					(ll)h[lst][j]*g[cnt[i]][k]%mo);
		lst=i;
	}
	
	int ans=0;
	for(i=1;i<=n;i++) ans=add(ans,(ll)h[lst][i]*mi(n,i-2)%mo);
	
	printf("%d\n",ans);
	
	return 0;
}
/*
给定 n 个有颜色的点,问能构成多少同色连通块大小 <=k 的无根树
一种显然的想法是枚举颜色 i 构成了 j 个大小不超过 k 的无根树
若一共有 m 个连通块,总方案数为 n^(m-2) * pro(siz[i])
但这样可能将同色连通块再连到一起
于是枚举最终连到一起的连通块大小,和其原本是多少个合法连通块,设为 x
这样的块容斥系数为 (-1)^(x-1)
对每一部分分别 dp,转移时钦定新枚举的连通块包含当前编号最大的点
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3932kb

input:

5 3
1
1
3
1
5

output:

125

result:

ok "125"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

4 2
2
1
1
1

output:

7

result:

ok "7"

Test #3:

score: 0
Accepted
time: 60ms
memory: 4648kb

input:

300 16
2
2
2
4
5
1
5
3
5
4
2
1
4
4
4
5
2
1
5
4
3
4
5
3
5
5
1
3
1
1
2
5
5
3
3
2
5
2
3
2
2
4
2
2
2
4
4
2
2
4
1
3
3
4
1
3
3
4
3
4
3
5
5
4
3
3
1
2
1
2
5
2
2
4
3
3
5
3
2
4
3
5
1
4
5
5
2
3
2
3
4
4
5
5
5
5
4
5
3
2
4
4
4
3
5
3
1
1
3
5
5
4
5
2
5
5
5
2
2
2
3
1
5
4
1
4
3
5
1
4
4
2
5
2
2
4
5
3
4
3
3
4
2
5
1
1
3...

output:

540253743

result:

ok "540253743"

Test #4:

score: 0
Accepted
time: 62ms
memory: 4648kb

input:

300 20
2
7
4
5
1
10
3
10
9
2
6
4
9
4
5
2
6
10
9
8
4
10
8
5
5
1
3
1
1
7
5
5
3
8
7
10
2
3
2
7
4
7
7
7
9
9
2
7
9
6
3
3
4
1
8
8
4
3
4
8
5
10
9
3
3
6
7
6
7
10
7
2
9
3
3
10
3
7
4
8
10
1
4
5
10
2
3
7
3
4
9
5
10
5
10
9
5
3
2
9
4
4
3
10
3
6
1
8
5
10
4
5
7
10
5
5
7
2
7
3
1
5
4
1
9
3
5
1
9
4
7
10
2
2
4
10
8
9
...

output:

616258392

result:

ok "616258392"

Test #5:

score: 0
Accepted
time: 50ms
memory: 4800kb

input:

300 1
124
25
131
70
63
150
139
62
46
94
9
34
25
102
66
120
139
28
134
120
98
135
95
21
43
71
11
87
45
15
33
58
37
70
12
63
132
47
104
97
67
17
9
119
72
87
29
96
53
103
34
71
58
78
34
3
94
78
115
60
139
43
63
46
127
146
37
60
37
12
59
23
43
120
53
107
54
68
70
21
94
125
10
22
143
117
133
64
129
55
14...

output:

450350134

result:

ok "450350134"

Test #6:

score: 0
Accepted
time: 50ms
memory: 4868kb

input:

300 2
131
70
63
150
139
62
46
94
9
34
25
102
66
120
139
28
134
120
98
135
95
21
43
71
11
87
45
15
33
58
37
70
12
63
132
47
104
97
67
17
9
119
72
87
29
96
53
103
34
71
58
78
34
3
94
78
115
60
139
43
63
46
127
146
37
60
37
12
59
23
43
120
53
107
54
68
70
21
94
125
10
22
143
117
133
64
129
55
140
75
10...

output:

942808207

result:

ok "942808207"

Test #7:

score: 0
Accepted
time: 131ms
memory: 4636kb

input:

300 150
1
2
2
2
1
2
1
2
2
2
1
2
2
2
2
1
1
1
1
1
1
1
1
1
1
2
1
2
2
1
2
1
2
1
1
1
1
1
2
1
1
2
1
1
2
1
2
2
2
1
2
2
1
2
1
1
1
2
1
2
1
2
1
2
1
1
1
2
1
1
2
2
2
1
2
1
2
2
1
1
1
2
1
1
2
1
2
1
1
1
2
1
2
2
1
2
1
2
1
2
1
2
2
1
1
2
1
1
1
2
1
1
1
1
2
1
1
1
1
1
1
2
1
2
2
2
2
2
2
1
1
1
2
2
1
1
1
1
1
2
1
1
2
1
1
1
...

output:

169425341

result:

ok "169425341"

Test #8:

score: 0
Accepted
time: 157ms
memory: 4544kb

input:

300 290
2
2
1
2
1
2
2
2
1
2
2
2
2
1
1
1
1
1
1
1
1
1
1
2
1
2
2
1
2
1
2
1
1
1
1
1
2
1
1
2
1
1
2
1
2
2
2
1
2
2
1
2
1
1
1
2
1
2
1
2
1
2
1
1
1
2
1
1
2
2
2
1
2
1
2
2
1
1
1
2
1
1
2
1
2
1
1
1
2
1
2
2
1
2
1
2
1
2
1
2
2
1
1
2
1
1
1
2
1
1
1
1
2
1
1
1
1
1
1
2
1
2
2
2
2
2
2
1
1
1
2
2
1
1
1
1
1
2
1
1
2
1
1
1
1
2
...

output:

394671363

result:

ok "394671363"

Test #9:

score: 0
Accepted
time: 157ms
memory: 4500kb

input:

300 290
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
...

output:

0

result:

ok "0"

Test #10:

score: 0
Accepted
time: 100ms
memory: 4680kb

input:

300 80
1
3
3
3
1
1
2
3
2
3
2
3
1
2
2
3
3
3
3
1
1
1
3
3
3
2
2
1
1
2
3
2
3
3
2
3
2
1
1
2
1
3
1
3
1
3
1
3
1
1
3
1
1
2
1
3
1
3
2
2
1
3
2
2
3
2
1
3
1
2
1
1
2
3
1
1
3
1
2
3
1
1
1
1
1
2
1
1
2
1
3
2
2
2
1
3
1
2
3
3
1
3
3
1
3
1
2
2
2
2
1
1
2
1
1
1
1
2
1
3
2
2
1
1
1
3
1
3
1
1
3
1
2
2
1
3
1
1
3
1
2
3
2
2
1
3
2...

output:

428950103

result:

ok "428950103"

Test #11:

score: 0
Accepted
time: 82ms
memory: 4684kb

input:

300 50
3
3
1
1
2
3
2
3
2
3
1
2
2
3
3
3
3
1
1
1
3
3
3
2
2
1
1
2
3
2
3
3
2
3
2
1
1
2
1
3
1
3
1
3
1
3
1
1
3
1
1
2
1
3
1
3
2
2
1
3
2
2
3
2
1
3
1
2
1
1
2
3
1
1
3
1
2
3
1
1
1
1
1
2
1
1
2
1
3
2
2
2
1
3
1
2
3
3
1
3
3
1
3
1
2
2
2
2
1
1
2
1
1
1
1
2
1
3
2
2
1
1
1
3
1
3
1
1
3
1
2
2
1
3
1
1
3
1
2
3
2
2
1
3
2
2
3...

output:

283683661

result:

ok "283683661"

Test #12:

score: 0
Accepted
time: 82ms
memory: 4628kb

input:

300 50
1
1
2
3
2
3
2
3
1
2
2
3
3
3
3
1
1
1
3
3
3
2
2
1
1
2
3
2
3
3
2
3
2
1
1
2
1
3
1
3
1
3
1
3
1
1
3
1
1
2
1
3
1
3
2
2
1
3
2
2
3
2
1
3
1
2
1
1
2
3
1
1
3
1
2
3
1
1
1
1
1
2
1
1
2
1
3
2
2
2
1
3
1
2
3
3
1
3
3
1
3
1
2
2
2
2
1
1
2
1
1
1
1
2
1
3
2
2
1
1
1
3
1
3
1
1
3
1
2
2
1
3
1
1
3
1
2
3
2
2
1
3
2
2
3
2
1...

output:

280919911

result:

ok "280919911"

Test #13:

score: 0
Accepted
time: 157ms
memory: 4560kb

input:

300 300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
...

output:

394671363

result:

ok "394671363"

Test #14:

score: 0
Accepted
time: 158ms
memory: 4636kb

input:

300 299
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
...

output:

0

result:

ok "0"