QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85492#990. Colorful Componentswind_crossAC ✓153ms4468kbC++142.0kb2023-03-07 20:06:532023-03-07 20:06:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-07 20:06:55]
  • 评测
  • 测评结果:AC
  • 用时:153ms
  • 内存:4468kb
  • [2023-03-07 20:06:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline char nc()
{
	static char buf[1000000],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,1000000,stdin),l==r)?EOF:*l++;
}
template <class code>inline code read(const code &a)
{
    code x=0;short w=0;char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=nc();}
    while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=nc();}
    return w?-x:x;
}
void print(long long x){
	if(x<0)putchar('-'),x=-x;
	if(x>=10)print(x/10);
	putchar(x%10+48);
}
const int mod=1e9+7;
int jc[305],inv[305],fa[305],kx[305][305],t[305];
int dp1[305],pw[305][305],dp[305];
int ksm(int x,int y){
	int now=1;
	while(y){
		if(y&1)now=1ll*now*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return now;
}
int main(){
    // freopen("text.in","r",stdin);
    // freopen("text.out","w",stdout);
	int n=read(n),k=read(k);
	for(int i=1;i<=n;i++){
		pw[i][0]=1;
		for(int j=1;j<=n;j++){
			pw[i][j]=1ll*pw[i][j-1]*i%mod;
		}
	}
	fa[1]=1;
	for(int i=2;i<=n;i++)fa[i]=ksm(i,i-2);
	jc[0]=1;
	for(int i=1;i<=n;i++)jc[i]=1ll*jc[i-1]*i%mod;
	inv[n]=ksm(jc[n],mod-2);
	for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
	kx[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int p=1;p<=j&&p<=k;p++){
				kx[i][j]=(kx[i][j]+1ll*kx[i-1][j-p]*fa[p]%mod*jc[j]%mod*p%mod*inv[p]%mod*inv[j-p])%mod;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)kx[i][j]=1ll*kx[i][j]*inv[i]%mod;
	}
	for(int i=1;i<=n;i++){
		int x=read(x);
		t[x]++;
	}
	dp[0]=1;
	int tot=0;
	for(int i=1;i<=n;++i) {
		if(!t[i])continue;
		int z=t[i];
		++tot;
		for(int j=0;j<=n;++j){
			for(int p=1;p<=z;++p){
				dp1[j+p]=(dp1[j+p]+1ll*dp[j]*kx[p][z]%mod*pw[n-z][p-1])%mod;
			}
		}
		memcpy(dp,dp1,sizeof(dp1));
		memset(dp1,0,sizeof(dp1));
	}
	if(tot==1){
		if(k==n)printf("%d\n",ksm(n,n-2));
		else printf("0\n");
		return 0;
	}
	int ans=0;
	for(int i=tot;i<=n;++i)ans=(ans+1ll*dp[i]*ksm(n,tot-2))%mod;
	printf("%d\n",ans);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3848kb

input:

5 3
1
1
3
1
5

output:

125

result:

ok "125"

Test #2:

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

input:

4 2
2
1
1
1

output:

7

result:

ok "7"

Test #3:

score: 0
Accepted
time: 16ms
memory: 4284kb

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: 19ms
memory: 4348kb

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: 4ms
memory: 4312kb

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: 5ms
memory: 4304kb

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: 94ms
memory: 4296kb

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: 140ms
memory: 4304kb

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: 133ms
memory: 4340kb

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: 61ms
memory: 4340kb

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: 49ms
memory: 4316kb

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: 40ms
memory: 4468kb

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: 153ms
memory: 4344kb

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: 131ms
memory: 4244kb

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"