Skip to content

11099: 【原1099】PerfectBall

题目

题目描述

author: Yan Liu 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1099

Description

LL has n (n <= 100) balls. Every ball has its own color which belongs to 1 .. C. Today, LL wants to put all his balls into some boxes. He has one rule that never puts two balls with different color into same box.

Note that any two boxes can't be distinguished. LL wants to know how many different ways to put his balls into boxes (you may assume that LL has infinitely number of boxes)?

Input Format

Input contains two line. The first line has two integers N and C, which means the number of balls and the number of colors. The second line has N integers, the i-th integer color_i represents the color ID of the i-th ball (1 <= color_i <= C)

Output Format

Output should have one line, contains an integer R, indicates the number of ways that LL puts his balls into boxes.

Sample Input 1

2 2
1 2

Sample Output 1

1

Sample Input 2

3 1
1 1 1

Sample Output 2

3

Case Limits

Time limit: 500 msec

Memory limit: 64 MB

zqy2018's solution

/*
    Hint: use integer partition
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
ll f[105][105] = {0}, tot[105];
int a[105], n, c;
void init(){
    n = read(), c = read();
    for (int i = 1; i <= n; ++i)    
        a[i] = read();
    sort(a + 1, a + n + 1);

    f[0][0] = 1;
    for (int i = 1; i <= 100; ++i){
        f[i][1] = 1;
        for (int j = 2; j <= i; ++j)
            f[i][j] = f[i - 1][j - 1] + f[i - j][j];
        tot[i] = 0;
        for (int j = 1; j <= i; ++j)
            tot[i] += f[i][j];
    }
}
void solve(){
    ll ans = 1;
    for (int i = 1; i <= n; ){
        int j = i;
        while (j <= n && a[i] == a[j])
            ++j;
        ans = 1ll * ans * tot[j - i];
        i = j;
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}