-
1284-C, *1600코드포스 2021. 11. 3. 03:13
Problem - C - Codeforces
codeforces.com
문제
- 수열 {a}={a1a2...an}에 대해 [l, r] 은 부분수열 {alal+1...ar}을 의미한다
- 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 가 되려면 al,al+1...ar은 연속된 수들의 조합이어야한다
예를 들어 [1, 3] 가 framed-segment 가 되려면 연속된 3개의 수, 가령 456 이 al,al+1...ar을 구성해야한다i) 구간의 크기가 1인 [l, r] ~ n⋅n!=1!n2(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!120!
[1, n]은 항상 framed-segment 이고 순열은 n! 개가 있다따라서 구하려고 하는값은
n∑i=1i!(n−i+1)2(n−i)!
1234567891011121314151617181920212223242526272829#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'코드포스' 카테고리의 다른 글
1295-C, *1600 (0) 2021.11.10 1295-B, *1700 (0) 2021.11.10 1284-B, *1400 (0) 2021.11.03 1604-B, *1100 (0) 2021.11.01 1604-C, *1300 (0) 2021.11.01