QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#451110 | #990. Colorful Components | Rikku_eq | WA | 26ms | 5268kb | C++14 | 1.4kb | 2024-06-22 21:08:51 | 2024-06-22 21:08:51 |
Judging History
answer
#include <bits/stdc++.h>
#define N 304
#define mod 1000000007
using namespace std;
typedef long long ll;
int n, K, cnt[N], c[N];
ll C[N][N], g[N], f[N][N], h[N];
ll pw (ll bs, ll t)
{
ll res=1;
while (t) {
if (t&1) { res=res*bs%mod; }
bs=bs*bs%mod; t>>=1;
}
return res;
}
int main ()
{
// freopen("0test.in", "r", stdin);
// freopen("0test.out", "w", stdout);
scanf("%d %d", &n, &K);
for (int i=1; i<=n; i++) { scanf("%d", &c[i]); cnt[c[i]]++; }
for (int i=0; i<=n; i++) {
C[i][0]=1;
for (int j=1; j<=i; j++) { C[i][j]=(C[i-1][j]+C[i-1][j-1]) %mod;}
}
f[1][1]=1; g[1]=1;
for (int k=2; k<=n; k++) {
g[k]=(k>K ? 0 : pw(k, k-2));
for (int i=2; i<=k; i++) {
for (int j=1; j<k; j++) {
f[k][i]+=f[k-j][i-1]*C[k-1][j-1] %mod *g[j] %mod;
}
g[k]-=f[k][i]*pw(k, i-2); f[k][1]%=mod;
}
f[k][1]=g[k]*k%mod; g[k]=g[k]*k%mod;
}
h[0]=1;
for (int i=1; i<=n; i++) if (cnt[i]) {
for (int j=n; j>=0; j--) {
h[j]=0;
for (int k=1; k<=j; k++) {
h[j]+=h[j-k]*f[cnt[i]][k] %mod;
h[j]%=mod;
}
}
}
ll ans=h[1];
for (int j=2; j<=n; j++) { ans+=h[j]*pw(n, j-2)%mod; ans%=mod; }
ans=(ans+mod)%mod;
printf("%lld\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
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: -100
Wrong Answer
time: 26ms
memory: 5268kb
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:
785973234
result:
wrong answer 1st words differ - expected: '540253743', found: '785973234'