시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 28 | 5 | 4 | 22.222% |
$f(n, k)$는 집합 $[n]$에서 모든 $k$-부분 집합을 구하고, 각 부분 집합에서 원소를 곱한 값을 모두 더한 값이다. 집합 $[n]$은 $1$보다 크거나 같고, $n$보다 작거나 같은 모든 자연수로 이루어진 집합이고, $k$-부분 집합은 크기가 $k$인 부분 집합이다. $f(n, k)$는 다음과 같은 수식으로 표현할 수 있다.
\[\sum_{S \subseteq [n], |S| = k}{\prod_{x \in S}{x}}\]
$f(n, 0) = 1$이다.
$f(n, k)$를 구하는 것은 지루하기 때문에, 재미있는 값을 구하려고 한다. 자연수 $n$과 소수 $p$가 주어졌을 때, $f(n, k)$가 $p$로 나누어 떨어지지 않는 $k$ $(0 \le k \le n)$의 개수를 구해보자.
첫째 줄에 정수 $n$과 소수 $p$가 주어진다.
문제 조건을 만족하는 $k$의 개수를 $10^9+7$로 나눈 나머지를 출력한다.
4 2
2
$f(4, k)$는 다음과 같다.
$k = 0$, $k = 2$인 경우만 $p = 2$로 나누어 떨어지지 않는다.