BOJ 25182 - 청정수열 (Hard)

image.png

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

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

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

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

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

그리고 점수는 직접 대충 1 2 3 3 2 11\ 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]);
}

Tags:

Categories:

Updated:

Comments