QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#422450 | #990. Colorful Components | MEKHANE | AC ✓ | 80ms | 6632kb | C++14 | 1.1kb | 2024-05-27 14:42:12 | 2024-05-27 14:42:13 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int N=305,mod=1e9+7;
int n,K,s,ans,pw[N][N],c[N][N],zs[N],f[N][N],f1[N][N],g[N],xs[N],inv[N];
signed main(){
ios::sync_with_stdio(false);
cin>>n>>K,inv[1]=1;
rep(i,2,n) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
rep(i,1,n){pw[i][0]=1; rep(j,1,n) pw[i][j]=pw[i][j-1]*i%mod;}
rep(i,0,n){c[i][0]=1; rep(j,1,i) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}
rep(i,1,n){int col; cin>>col,zs[col]++;}
f[0][0]=f1[0][0]=g[0]=1;
rep(i,1,n) rep(j,1,i){
rep(k,1,min(K,i)) f[i][j]=(f[i][j]+f[i-k][j-1]*(k==1?1:pw[k][k-2])%mod*c[i-1][k-1]%mod*k)%mod;
xs[i]=(xs[i]+(((j-1)&1)?mod-1:1)*(j==1?inv[i]:pw[i][j-2])%mod*f[i][j])%mod;
}
rep(i,1,n) rep(j,1,i) rep(k,1,i) f1[i][j]=(f1[i][j]+f1[i-k][j-1]*xs[k]%mod*c[i-1][k-1]%mod*k)%mod;
rep(i,1,n) if(zs[i]){
per(j,s,0){
rep(k,1,zs[i]) g[j+k]=(g[j+k]+g[j]*f1[zs[i]][k])%mod;
g[j]=0;
}s+=zs[i];
}
rep(i,1,n) ans=(ans+g[i]*(i==1?inv[n]:pw[n][i-2]))%mod;
cout<<ans;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3748kb
input:
5 3 1 1 3 1 5
output:
125
result:
ok "125"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
4 2 2 1 1 1
output:
7
result:
ok "7"
Test #3:
score: 0
Accepted
time: 35ms
memory: 6620kb
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: 33ms
memory: 6500kb
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: 40ms
memory: 6572kb
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: 39ms
memory: 6632kb
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: 67ms
memory: 6616kb
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: 6632kb
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: 80ms
memory: 6560kb
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: 56ms
memory: 6552kb
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: 46ms
memory: 6612kb
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: 6516kb
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: 80ms
memory: 6540kb
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: 72ms
memory: 6500kb
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"