Problems
BOJ 23871 HILO

BOJ 23871 HILO

문제 링크:

문제 내용

양의 정수 NN과 0≤x≤N0 \le x \le N인 정수 xx가 주어집니다. 앨리스는 x+0.5x + 0.5의 값을 가지고 있고, 밥은 다음의 과정을 거쳐서 앨리스가 갖고 있는 수를 알아내려 합니다.

  1. 먼저 길이 NN의 순열을 하나 정합니다.
  2. 그 순열에서 아직 부르지 않은 수 중에서 첫 번째 수를 부릅니다. 앨리스는 밥이 부른 수가 앨리스의 수보다 크다면 “HI"를, 작다면 “LO"를 말합니다.
  3. 앨리스가 “HI"를 말했다면, 방금 부른 수보다 큰 모든 수를 순열에서 제거합니다. “LO"라면, 방금 부른 수보다 작은 모든 수를 순열에서 제거합니다. 더 이상 부를 수가 없을 때까지 2번으로 돌아가 반복합니다.

모든 가능한 순열에 대해, 앨리스가 “HI” 직후 “LO"를 부르게 되는 횟수의 총합을 구하세요.

입력

첫 줄에 NN과 xx가 주어집니다. (1≤N≤50001 \le N \le 5000, 0≤x≤N0 \le x \le N)

출력

문제의 정답을 109+710^9+7로 나눈 나머지를 출력합니다.

문제 풀이

스포일러

다음과 같은 DP식을 세울 수 있습니다. lo(N,x)lo(N,x)는 현재 상황 직전에 LO를 불렀거나 그것과 동등한 상황일 때 그 이후에 HILO가 불리는 횟수의 합, hi(N,x)hi(N,x)는 직전에 HI를 부른 상황일 때 그 HI를 포함하여 HILO가 불리는 횟수의 합입니다.

lo(N,x)=∑i=1xN−1Pi−1lo(N−i,x−i)+∑i=x+1NN−1PN−ihi(i−1,x)hi(N,x)=∑i=1xN−1Pi−1lo(N−i,x−i)+∑i=x+1NN−1PN−ihi(i−1,x)+x(N−1)! \begin{align*} lo(N,x) &= \sum_{i=1}^{x} {_{N-1}}P_{i-1} lo(N-i,x-i) \\ &+ \sum_{i=x+1}^{N} {_{N-1}}P_{N-i} hi(i-1,x) \\ hi(N,x) &= \sum_{i=1}^{x} {_{N-1}}P_{i-1} lo(N-i,x-i) \\ &+ \sum_{i=x+1}^{N} {_{N-1}}P_{N-i} hi(i-1,x) + x (N-1)! \\ \end{align*}

이 식을 해석하면 다음과 같습니다.

  • xx 이하의 수 ii를 부르면 LO를 부르며, 이때 ii 미만의 수(i−1i-1개)들은 남은 위치 중 어디에 있든지 상관 없습니다. 이들의 위치를 선택하는 방법은 N−1N-1개의 자리 중 i−1i-1개를 순서대로 선택하는 방법의 수와 같습니다.
  • xx 초과인 수 ii를 부르면 HI를 부르며, 이때 ii 초과인 수(N−iN-i개)에 대해 같은 논리를 적용할 수 있습니다.
  • 직전에 HI를 불렀을 때, 이번에 LO를 부르는 경우의 수는 (첫 수를 고르는 방법의 수) ×\times (나머지 수를 배열하는 방법의 수) =x(N−1)!= x (N-1)!입니다.

이제 두 개의 sum을 빠르게 구해야 합니다. 이는 다음을 이용해 각각 O(1)\mathcal{O}(1)에 처리할 수 있습니다.

∑i=1xN−1Pi−1lo(N−i,x−i)=lo(N−1,x−1)+(N−1)∑i=2xN−2Pi−2lo(N−i,x−i)=lo(N−1,x−1)+(N−1)∑i=1x−1N−2Pi−1lo(N−i−1,x−i−1) \begin{align*} &\sum_{i=1}^{x} {_{N-1}}P_{i-1} lo(N-i,x-i) \\ =& lo(N-1, x-1) + (N-1)\sum_{i=2}^{x} {_{N-2}}P_{i-2} lo(N-i,x-i) \\ =& lo(N-1, x-1) + (N-1)\sum_{i=1}^{x-1} {_{N-2}}P_{i-1} lo(N-i-1,x-i-1) \end{align*}
Last updated on
BOJ 2385 Secret SharingBOJ 23894 합성함수와 쿼리 2