2021. 8. 15. 18:26ㆍPS/백준
이 문제에서 구하려는 함수는 다음과 같다.
함수 $S$는 다음과 같이 정의된다.
- $S(0,\ n) = n$ (모든 양의 정수 $n$)
- $S(k,\ n) = S(k-1,\ 1) + S(k-1,\ 2) + ... + S(k-1,\ n)$ (모든 양의 정수 $k,\ n$)
이때 $S(k, n)$을 적절히 변형시켜보자.
$S(k,\ n) = S(k-2,\ 1) + [S(k-2,\ 1) + S(k-2,\ 2)] + [S(k-2,\ 1)+S(k-2,\ 2)+S(k-2,\ 3)] + ...$
$= nS(k-2,\ 1) + (n-1)S(k-2,\ 2) + (n-2)S(k-2,\ 3) + ... $
정의에 의해서
$= nS(k-3,\ 1) + (n-1)[S(k-3,\ 1)+S(k-3,\ 2)] + (n-2)[S(k-3,\ 1)+S(k-3,\ 2)+S(k-3,\ 3)]+...$
각 계수를 조합으로 적절히 변형시켜주면
$=_{n}\mathrm{C}_{1}\ S(k-3,\ 1)+_{n-1}\mathrm{C}_{1}\ [S(k-3,\ 1)+S(k-3,\ 2)] +_{n-2}\mathrm{C}_{1}\ [S(k-3,\ 1)+S(k-3,\ 2)+S(k-3,\ 3)]+...$
하키스틱 정리를 적용하면
$=_{n+1}\mathrm{C}_{2}\ S(k-3,\ 1)+_{n}\mathrm{C}_{2}\ S(k-3,\ 2) +_{n-1}\mathrm{C}_{2}\ S(k-3,\ 3)+...$
위와 같은 과정을 반복하면
$=_{n+p}\mathrm{C}_{p+1}\ S(k-p-2,\ 1)+_{n+p-1}\mathrm{C}_{p+1}\ S(k-p-2\ ,2) +_{n+p-2}\mathrm{C}_{p+1}\ S(k-p-2,\ 3)+...$
$k-p-2=0$이라고 한다면 $p=k-2$이다.
이때 식은
$=_{n+k-2}\mathrm{C}_{k-1}\ S(0,\ 1)+_{n+k-3}\mathrm{C}_{k-1}\ S(0\ ,2) +_{n+k-4}\mathrm{C}_{k-1}\ S(0,\ 3)+...$
정의에 의해
$=_{n+k-2}\mathrm{C}_{k-1}+2_{n+k-3}\mathrm{C}_{k-1} +3_{n+k-4}\mathrm{C}_{k-1}+...$
이것은 조합의 뒷 숫자가 $k-1$인 것들의 합이므로 하키스틱 정리를 이용할 수 있다. 조합의 앞 숫자가 $k-1$인 것이 $n$개 존재하므로 조합의 앞 숫자가 $k-1$인 것부터 $n+k-2$까지, $k-1$인 것부터 $n-k-3$까지 ... 이런 방식으로 따로 따로 하키스틱 정리를 적용시킬 수 있다. 이를 적용하면
$=_{n+k-1}\mathrm{C}_{k}+_{n+k-2}\mathrm{C}_{k} +_{n+k-3}\mathrm{C}_{k}+...$
다시 하키스틱 정리를 적용하면
$=_{n+k}\mathrm{C}_{k+1}$
$\therefore S(n,\ k) =_{n+k}\mathrm{C}_{k+1}$
이제 조합을 계산하기만 하면 끝!
코드는 다음과 같다.
# 코드 보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<stdio.h>
typedef long long int lo;
lo p=1e9+7;
lo pow(lo n,lo k){
lo s=1,h=n;
for(;k;k>>=1){
if(k&1) s=s*h%p;
h=h*h%p;
}
return s;
}
lo fac(lo n){
lo s=1,i;
for(i=1;i<=n;i++){
s=s*i%p;
}
return s;
}
int main(){
lo n,k,s=1,i;
scanf("%lld %lld",&k,&n);
for(i=n;i<=n+k;i++){
s=s*i%p;
}
s=s*pow(fac(k+1),p-2)%p;
printf("%lld",s);
}
|
cs |
# 닫기
'PS > 백준' 카테고리의 다른 글
[BOJ 1770] 배수와 약수의 개수 (7) | 2021.08.21 |
---|---|
[BOJ 11778] 피보나치 수와 최대공약수 (1) | 2021.08.21 |
[BOJ 10908] Phibonacci (0) | 2021.08.21 |
[BOJ 19577] 수학은 재밌어 (0) | 2021.08.16 |
[BOJ 4798] 등차수열에 관한 디리클레의 정리 (1) | 2021.06.02 |