QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#451110#990. Colorful ComponentsRikku_eqWA 26ms5268kbC++141.4kb2024-06-22 21:08:512024-06-22 21:08:51

Judging History

你现在查看的是最新测评结果

  • [2024-06-22 21:08:51]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:5268kb
  • [2024-06-22 21:08:51]
  • 提交

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'