문제
BOJ 1722(https://www.acmicpc.net/problem/1722)
$\lbrace 1, 2, 3, 4, … , n \rbrace$을 시작으로 하는 순열이 있다.
현재 순열의 상태에서 다음 순열의 상태로 가는 연산이 C++의 next_permutation과 같이 동작 할 때 해당 순열이 몇 번째인지, 혹은 $k$번째 순열이 무엇인지 구해야한다.
풀이
순열을 각 자리로 쪼개서 생각해보자.
현재 순열에서 $i$번째 자리의 숫자가 $1$단계 증가하려면 몇 번의 순열 증가 연산을 거쳐야 할까?
(이 때 $1$단계 증가한다는 것은 단순히 숫자가 1 증가한다는 것이 아니라 $A[1..i)$와 $A(i..n]$ 각각의 순서 관계는 변함 없이 순수하게 $A[i]$만 한 단계 상승하는 것을 의미한다.
예를 들어, $\lbrace 2, 1, 3, 4 \rbrace$가 있으면 $i = 2$일 때 $\lbrace 2, 3, 1, 4 \rbrace$로 증가하는 것을 의미한다.)
이 경우는 당연히 $i$번째 이전 자리는 건들 필요가 없으니 $i$이후의 자리가 몇 번이나 바뀌는지를 봐야 하는데, $(n-i)!$만큼의 연산이 필요하다는 것을 알 수 있다.
따라서 $k$번째 순열을 알아야 한다면 초기 수열에서 시작해 가장 앞의 자리수부터 k이하의 되는 선에서 최대한 증가시키는 것을 반복해나가면 된다.
또한 $A$가 몇 번째 순열인지 알아내는 것도 마찬가지로 가장 앞의 자리수부터 이 자리수가 몇 번이나 증가된 것인지를 알아내어 더해가는 것을 반복하면 된다.
(이 때, $k$가 $1$-indexed 라는 것에 주의해서 구현해야 한다.)
소스코드
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
int n;
i64 f[21];
vi ar, rem;
void input() {
cin >> n;
}
int solve() {
f[0] = 1;
FOR(i, 1, 21) f[i] = f[i-1] * i;
FOR(i, 0, n) rem.pb(i+1);
int tt; cin >> tt;
if(tt == 1) {
i64 k; cin >> k; --k;
FOR(i, 0, n) {
ar.pb(rem[k/f[n-i-1]]);
rem.erase(rem.begin() + k/f[n-i-1]);
k %= f[n-i-1];
}
FOR(i, 0, n) cout << ar[i] << ' '; cout << ENDL;
} else {
ar.resize(n);
FOR(i, 0, n) cin >> ar[i];
i64 ans = 1;
FOR(i, 0, n) {
auto it = lower_bound(ALL(rem), ar[i]);
ans += f[n-i-1] * (it-rem.begin());
rem.erase(it);
}
cout << ans << ENDL;
}
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //