QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#85492 | #990. Colorful Components | wind_cross | AC ✓ | 153ms | 4468kb | C++14 | 2.0kb | 2023-03-07 20:06:53 | 2023-03-07 20:06:55 |
Judging History
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"