BOJ 25182 - 청정수열 (Hard)

BOJ 25182 - 청정수열 (Hard)

$1,2,1,2$ 를 고려한다.

$(1+2+1)\cdot 1 + (2+1+2) \cdot 2$이다.

그리고 $1,1,2,2$나 $2,2,1,1$ 을 제외하고는 어떻게 배치하든 값이 같다.

이를 귀납적으로 따져보면 최대 점수가 나오려면 항상 모든 수들의 사이에 다른 모든 수가 끼어있기만 하면 된다는 것을 추측할 수 있다.

그럼 $n! \cdot n!$ 의 가지수가 나오게 된다.

그리고 점수는 직접 대충 $1\ 2 \ 3 \cdots \ 3\ 2\ 1$ 처럼 배치해둔다 생각하고 구하면 된다.

const int mod = 1e9 + 7;
inline int md(int x){
   return md(mod, x);
};
int fac[100001];
void solve() {
   int n;
   cin >> n;
   fac[0] = 1;
   for(int i = 1; i <= 100000; i++) fac[i] = md(fac[i-1] * i);

   int v = 0, sum = 2 * n * (n + 1) / 2;
   for(int i = n; i >= 1; i--){
      v = md(v + sum * i);
      sum -= 2 * i;
   }

   cout << v << ' ' << md(fac[n] * fac[n]);
}