QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#423207 | #990. Colorful Components | OvO_Zuo | AC ✓ | 158ms | 4868kb | C++14 | 2.4kb | 2024-05-27 21:32:48 | 2024-05-27 21:32:50 |
Judging History
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"