#define MOD 1000000007
static int N;
static int table[1001];
static void table_init()
{
long long cur = 0;
long long factorial = 1;
for (int i = 1; i <= 1000; i++)
{
cur = i * cur;
cur += (i / 2) * factorial;
cur %= MOD;
table[i] = (int)cur;
factorial *= i;
factorial %= MOD;
}
}문제의 답을 구하기 위한 점화식은 아래와 같다.
f(0) = 0, n >= 1 에 대해서
f(n) = n * f(n - 1) + [n / 2] * (n - 1)!
이와 같이 식을 세운 이유는 아래와 같다.
먼저 N = 4에 대해서 4를 놓는 위치에 대해 생각해보자. (x, y, z 는 1 ~ 3 중 중복되지 않는 하나의 값)
4 x y x
x 4 y z
x y 4 z
x y z 4
첫번째 경우에 대해서 4는 절대 뒤집히지 않는다.
case1 == f(3)
두번째 경우에서 4는 한번 뒤집힌다.
case2 == f(3) + 3!
여기서 3!이 더해지는 이유는 다음과 같다.
N = 3 일 때 나열하는 모든 경우는 3! = 6 이다.
여기에서는 뒤집힌 동전이 없는 경우, 1개인 경우, 2개인 경우가 있고, 이 모든 경우들에 4가 뒤집혔기 때문에 1을 각각 더해주어야 한다.
그래서 총 3!이 더해지는 것과 같은 것이다.
세번째, 네번째 경우도 이와 같은 방식으로 그 경우의 수를 구할 수 있다.
이제 이를 수식으로 정리해보면 다음과 같이 구할 수 있다.
f(n) --> f(n-1) + {f(n-1) + (n-1)!} + f(n-1) + {f(n-1) + (n-1)!} ... + f(n-1) + {f(n-1) + (n-1)!} n == even
--> f(n-1) + {f(n-1) + (n-1)!} + f(n-1) + {f(n-1) + (n-1)!} ... + f(n-1) n == odd
= f(n) = n * f(n - 1) + [n / 2] * (n - 1)!
[n / 2] 는 int형 나눗셈으로 구할 수 있기 때문에 코드에서는 단순 나누기 2로 처리 할 수 있다.
또, f(n)은 최대 10억 6이 될 수 있고, f(n + 1)을 구할 때, n >= 4 이상만 되어도 오버플로우가 발생한다.
그래서 먼저 long long 형에 저장하는 것이다.
팩토리얼을 구하는 것도 마찬가지이다.
