7118 : 조합론 종합 2
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
조합론 분야의 보다 고도화된 수치들을 계산하는 프로그램을 작성하십시오.
각 줄에 주어지는 다음 세 가지 명령을 처리해야 합니다.
-
-
-
각 줄에 주어지는 다음 세 가지 명령을 처리해야 합니다.
-
STARS n k: 중복조합 H(k, n) mod 1,000,000,007 (n개의 동일 물건을 k개의 구별된 칸에 넣기)-
PARTITION n: 정수 분할 수 P(n) mod 1,000,000,007-
PIE n p1 p2 ...: 1부터 n까지의 정수 중 소수 p_i들의 배수의 개수 (포함배제 PIE 적용)입력 설명
첫째 줄에 명령의 개수 $N$이 주어집니다. ($1 \le N \le 100$)
둘째 줄부터 $N$개의 줄에 걸쳐 명령이 하나씩 주어집니다.
STARS의 $n, k$는 $1$ 이상 $1{,}000$ 이하, PARTITION의 $n$은 $1$ 이상 $200$ 이하, PIE의 $n$은 $10^9$ 이하이며 소수들의 개수 $K$는 $1$ 이상 $4$ 이하입니다.
출력 설명
각 명령에 대한 결과를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
STARS 5 3
PARTITION 5
PIE 100 2 3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
21
7
74도움
STARS는 중복조합 H(k, n) = C(k+n-1, n)을, PARTITION은 DP 정수 분할을, PIE는 포함배제 코드를 취합하여 구현하십시오.