선물 전달

Problem link: https://www.acmicpc.net/problem/1947

완전순열(교란 순열이라고도 불리는...) 문제이다.

결론부터 이야기하면 N개 원소에 대한 완전순열의 수 점화식은 아래와 같다.

• CACHE[N] = (N - 1) * (CACHE[N-1] + CACHE[N - 2])

점화식 유도는 아래와 같다.

수열이 아래와 같이 주어졌다고 해보자.

• {1, 2, 3, ... N-2, N-1, N}

편의상 1번 원소를 기준으로 점화식을 유도해보자(자명하게 다른 원소를 기준으로 유도해도 일반성을 잃지 않는다)

전체 경우의 수는 Case 1, Case 2의 합이 된다.

• Case 1) 1번 원소와 X번 원소(X in [2, N])가 서로 선물을 맞바꾼 경우
  • 예시로 그리면 아래와 같은 경우가 될 것이다.
  • 1번 원소와 X번 원소의 선물 교환이 아래 테이블과 같이 고정되었으므로 Case 1)에 해당되는 경우의 수는 사실 {2, 3, ..., X-1, X+1, ..., N-2, N-1, N} 수열의 완전순열 경우의 수와 같을 것이다.
    (1번 원소와 X번 원소를 빼놓은 수열임에 주의하자.)
  • 따라서, X번 원소를 고르는 경우의 수 N-1에 CACHE[N-2]를 곱하여 (N-1)*CACHE[N-2]을 얻는다.

1	2	3	...	X	...	N-2	N-1	N
X				1

• Case 2) 1번 원소는 X번 원소(X in [2, N])에게 설물을 주었지만 X번 원소`는 다른 사람에게 선물을 준 경우
  • 이 경우는 아래 테이블의 {2, 3, ..., X, ... N-2, N-1, N} 열에 {1, 2, 3, ..., X-1, X+1, ..., N-2, N-1, N}을 채워 넣는 경우의 수를 구하면 된다.
  • 단, Case 1)을 별도로 고려해주었기 때문에 X번 원소는 1번 원소에게 선물을 주면 안되므로 X열에는 1이 들어가면 안된다.
  • 잘 생각해보면 1이 그냥 X의 역할을 하는 N-1개 원소의 완전순열 경우의 수와 같음을 알 수 있다.
  • 따라서, X번 원소를 고르는 경우의 수 N-1에 CACHE[N-1]를 곱하여 (N-1)*CACHE[N-1]을 얻는다.

1	2	3	...	X	...	N-2	N-1	N
X

#include <iostream>
#include <cstdint>

using namespace std;

uint64_t kMod = 1000000000;
uint64_t N;

uint64_t Solve(void)
{
  if (N == 1)
  {
    return 0;
  }
  else if (N == 2)
  {
    return 1;
  }

  uint64_t pp = 0;
  uint64_t p = 1;

  uint64_t ans = 0;
  for (uint64_t it = 3; it <= N; ++it)
  {
    ans = ((it - 1) * ((p + pp) % kMod)) % kMod;
    pp = p;
    p = ans;
  }

  return ans;
}

int main(void)
{
  cin >> N;
  cout << Solve() << '\n';

  return 0;
}