QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#422717 | #990. Colorful Components | DaiRuiChen007 | AC ✓ | 80ms | 6792kb | C++14 | 1.3kb | 2024-05-27 18:56:43 | 2024-05-27 18:56:43 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=305,MOD=1e9+7;
ll ksm(ll a,ll b=MOD-2,ll p=MOD) {
if(b<0) b+=MOD-1;
ll ret=1;
for(;b;a=a*a%p,b>>=1) if(b&1) ret=ret*a%p;
return ret;
}
int a[MAXN];
ll C[MAXN][MAXN],tr[MAXN],g[MAXN][MAXN],h[MAXN],f[MAXN][MAXN],dp[MAXN][MAXN],ans;
signed main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1,p;i<=n;++i) scanf("%d",&p),++a[p];
for(int i=0;i<=n;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
for(int i=2;i<=n;++i) tr[i]=ksm(i,i-2); tr[1]=1;
g[0][0]=1;
for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) {
for(int k=1;k<=min(i,m);++k) {
g[i][j]=(g[i][j]+g[i-k][j-1]*tr[k]%MOD*C[i-1][k-1]%MOD*k)%MOD;
}
h[i]=(h[i]+MOD+(j&1?1:-1)*g[i][j]*ksm(i,j-2)%MOD)%MOD;
}
f[0][0]=1;
for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) {
for(int k=1;k<=i;++k) {
f[i][j]=(f[i][j]+f[i-k][j-1]*h[k]%MOD*C[i-1][k-1]%MOD*k)%MOD;
}
}
dp[0][0]=1;
for(int i=1;i<=n;++i) {
if(!a[i]) {
memcpy(dp[i],dp[i-1],sizeof(dp[i]));
continue;
}
for(int j=1;j<=n;++j) {
for(int k=1;k<=min(j,a[i]);++k) {
dp[i][j]=(dp[i][j]+dp[i-1][j-k]*f[a[i]][k])%MOD;
}
}
}
for(int i=1;i<=n;++i) ans=(ans+dp[n][i]*ksm(n,i-2))%MOD;
printf("%lld\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3964kb
input:
5 3 1 1 3 1 5
output:
125
result:
ok "125"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
4 2 2 1 1 1
output:
7
result:
ok "7"
Test #3:
score: 0
Accepted
time: 44ms
memory: 6656kb
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: 37ms
memory: 6792kb
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: 38ms
memory: 6660kb
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: 37ms
memory: 6728kb
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: 62ms
memory: 6660kb
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: 75ms
memory: 6792kb
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: 75ms
memory: 6712kb
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: 55ms
memory: 6788kb
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: 50ms
memory: 6692kb
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: 47ms
memory: 6788kb
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: 79ms
memory: 6792kb
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: 80ms
memory: 6736kb
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"