BOJ 25182 - 청정수열 (Hard)
를 고려한다.
이다.
그리고 나 을 제외하고는 어떻게 배치하든 값이 같다.
이를 귀납적으로 따져보면 최대 점수가 나오려면 항상 모든 수들의 사이에 다른 모든 수가 끼어있기만 하면 된다는 것을 추측할 수 있다.
그럼 의 가지수가 나오게 된다.
그리고 점수는 직접 대충 처럼 배치해둔다 생각하고 구하면 된다.
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]);
}
Comments