백준 30354번: Sum of Product of Binomial Coefficients

https://www.acmicpc.net/problem/30354

30354번: Sum of Product of Binomial Coefficients

---

문제의 설명을 읽어봤을 때, 진짜 모든 $a_{1}$ 부터 $a_{k}$ 에 대해 이항계수를 구할 순 없을 것 같습니다.

 

조합론적으로 접근했을 때, $f(k)$ 의 의미를 조금 더 와닿게 바꿀 수 있습니다.

 

$N$ 개 중에서 $a_{1}$ 개를 뽑는다.

$a_{1}$ 개 중에서 $a_{2}$ 개를 뽑는다.

$\vdots$

$a_{k-1}$ 개 중에서 $a_{k}$ 개를 뽑는다.

 

이러한 경우의 수는 어떻게 구할 수 있을까요?

 

벤다이어그램을 가져와도 편하게 구할 수 있고, 이 글에서는 stars-and-bars problem으로 바꿔보겠습니다.

 

이 경우 $f(k)$ 는 $k$ 개의 bars 를 놓고, 그 사이 $k+1$ 개의 공간을 $N$ 개의 stars 가 임의로 선택하는 경우의 수가 됩니다.

 

따라서, 각 테스트 케이스의 답은 다음과 같습니다.

$$ answer(N,K) = \sum_{i=2}^{K+1} i^{N} $$

이런 식에 관해서 Faulhaber's formula 등이 알려져있지만, 이 문제와 같이 $K$ 가 작고 $N$ 이 큰 경우 적용이 힘들겠습니다.

 

또한, 테스트 케이스의 $K$ 의 합의 상한이 $2 \times 10^{5}$ 이므로, $O((\sum K) \times log N)$ 복잡도로도 통과할 수 있게 됩니다.

 

이상을 구현하면 AC를 받을 수 있습니다. 아래는 제 코드입니다.

#include <iostream>
#define mod 998244353

long long power_modular (long long X, long long Y) {
	long long result = 1;
	while (Y) {
		if (Y % 2) {
			result = result * X % mod;
		}
		X = X * X % mod;
		Y /= 2;
	}
	return result;
}

using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int T;
	cin >> T;
	while (T--) {
		long long N, K;
		cin >> N >> K;
		
		long long answer = 0;
		for (long long i = 2; i <= K + 1; i++) {
			answer = (answer + power_modular(i, N)) % mod;
		}
		cout << answer << '\n';
	}
	return 0;
}

(C++20, 52ms, 2020KB, 제출번호 69072392)

---

$f(k)$ 에 관해 수식으로 접근할 수도 있습니다.

 

예를 들어 다음과 같은 방법이 있습니다.

$$ f(1) = \sum_{i=0}^{N} \binom{N}{i} = 2^{N} $$

$$ f(2) = \sum_{i=0}^{N} \left \{ \binom{N}{i} \sum_{j=0}^{i} \binom{i}{j} \right \} = \sum_{i=0}^{N} \left \{ \binom{N}{i} \times 2^{i} \right \} = 3^{N} $$

$$ \vdots $$

또 다른 방법으로는, $f(k)$ 의 정의로부터 다음을 얻고

$$ f(k) = \sum_{x_{0}+x_{1}+x_{2}+\cdots+x_{K} = N} \frac{N!}{x_{0}! \; x_{1}! \; x_{2}! \; \cdots \; x_{K}!}$$

여기에 Multinomial Theorem 을 쓰면 곧바로 $f(k)$ 를 얻을 수 있습니다.

 

벤다이어그램으로 생각할 때, 직사각형 안에 동심원이 $k$ 개 있는 모습을 상상합니다. 이때 생기는 $k+1$ 개의 서로 다른 위치에 $N$ 개의 숫자를 자유롭게 배치하는 경우의 수가 $f(k)$ 가 됩니다.

 

이 모든 방법으로 $f(k) = (k+1)^{N}$ 임을 동일하게 얻을 수 있습니다.