집합의 개수

Problem link: https://www.acmicpc.net/problem/2092

조금 헤메이기는 했는데, 그래도 결과적으로는 잘 풀어냈다.

DP로 접근하여 풀 수 있는 문제로 우선 아래와 같이 CACHE를 정의해준다.

• CACHE[t][k]: t 이하의 수들만을 사용하여 원소의 수가 k개인 집합을 만드는 경우의 수

주어진 수열에 존재하는 t의 수를 CNT[t]라고 할 때, 아래와 같이 점화식을 세워볼 수 있다.

• CACHE[t][k] = SUM(CACHE[t-1][k-l]), (0 <= l <= CNT[t])

점화식의 의미는 결국 t를 포함하지 않는 집합들에 l (0 <= l <= CNT[t])개의 t를 덧붙인 경우의 수를 헤아리겠다는 것과 같다.

한 가지 주의할 점으로는 기저사례 정의가 있는데, 공집합을 만드는 경우의 수는 항상 1개임을 기억하도록 하자.

#include <iostream>
#include <algorithm>

using namespace std;

const size_t kMod = 1000000;
const size_t kMaxA = 4000;
const size_t kMaxT = 200;

size_t T, A, S, B;

size_t CNT[kMaxT + 1];
size_t CACHE[kMaxT + 1][kMaxA + 1];

size_t Solve(void)
{
  CACHE[0][0] = 1;

  for (size_t t = 1; t <= T; ++t)
  {
    for (size_t k = 0; k <= A; ++k)
    {
      for (size_t num_of_ts = 0; num_of_ts <= CNT[t] && k >= num_of_ts; ++num_of_ts)
      {
        CACHE[t][k] = (CACHE[t][k] + CACHE[t - 1][k - num_of_ts]) % kMod;
      }
    }
  }

  size_t ret = 0;
  for (size_t k = S; k <= B; ++k)
  {
    ret = (ret + CACHE[T][k]) % kMod;
  }

  return ret;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Inputs
  cin >> T >> A >> S >> B;
  for (size_t it = 0; it < A; ++it)
  {
    size_t number;
    cin >> number;
    ++CNT[number];
  }

  // Solve
  cout << Solve() << '\n';

  return 0;
}