1284-C, *1600

Problem - C - Codeforces

문제

• 수열 $\left \{ a \right \}=\left \{ a_{1}a_{2}...a_{n} \right \}$에 대해 [l, r] 은 부분수열 $\left \{ a_{l}a_{l+1}...a_{r} \right \}$을 의미한다
• $\mathrm{max[l,\ r]-min[l,\ r]}=l-r$을 만족하는 [l, r]을 framed-segment 라고 한다
• 길이가 n 인 모든 n-permutation 에 대해 framed-segment 의 개수는?

 

$O(n)$

순열을 고정하여 framed-segment 를 구하지 말고
l, r 이 고정되어 있을 때 [l, r]이 framed-segment 가 되는 순열의 개수를 생각한다

[l, r]이 framed-segment 가 되려면 $a_{l},a_{l+1}...a_{r}$은 연속된 수들의 조합이어야한다
예를 들어 [1, 3] 가 framed-segment 가 되려면 연속된 3개의 수, 가령 456 이 $a_{l},a_{l+1}...a_{r}$을 구성해야한다

i) 구간의 크기가 1인 [l, r] ~ $n\cdot n!  = 1!n^{2}(n-1)!$
[1, 1]가 framed-segment 인 순열은 n! 개가 있다
또한 구간의 크기가 1인 [l, r]은 n개 있다

ii) 구간의 크기가 2인 [l, r] ~ $2!(n-1)^{2}(n-2)!$
[1, 2]가 framed-segment 인 순열은 (n-1)2!(n-2)! 개가 있다
또한 구간의 크기가 2인 [l, r]은 (n-1)개 있다

iii) 구간의 크기가 3인 [l, r] ~ $3!(n-2)^{2}(n-3)!$
[1, 3]가 framed-segment 인 순열은 (n-2)3!(n-3)! 개가 있다
또한 구간의 크기가 2인 [l, r]은 (n-2)개 있다

last) 구간의 크기가 n인 [l, r] ~ $n!=n!1^2 0!$
[1, n]은 항상 framed-segment 이고 순열은 n! 개가 있다

따라서 구하려고 하는값은

$$\sum_{i=1}^{n}i!(n-i+1)^{2}(n-i)!$$

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n, m;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    vector<ll> fac(n+1);
    fac[0] = 1;
    loop(i, n) fac[i] = fac[i-1]*i%m;
 
    ll res = 0;
    loop(i, n) res = (res + (fac[i]*(n-i+1)%m)*((n-i+1)*fac[n-i]%m))%m;
 
    cout << res << endl;
 
    return 0;
}cs