Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int cnt1 = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
cnt1 += (x == 1);
}
cout << n - cnt1 / 2 << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
a1, a2, a3, a4 = map(int, input().split())
if a1 == 0:
print(1)
else:
print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4))
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> pos(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
pos[x] = i;
}
int l = (n + 1) / 2, r = (n + 2) / 2;
while (l > 0 && (l == r || (pos[l] < pos[l + 1] && pos[r - 1] < pos[r]))) {
--l;
++r;
}
cout << (n - r + l + 1) / 2 << '\n';
}
}
1792D - Перестановки с неподвижным префиксом
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
int get(const vector<int> &a, const vector<int> &b){
int res = 0;
while (res < int(a.size()) && a[res] == b[res])
++res;
return res;
}
int main(){
int t;
scanf("%d", &t);
while (t--){
int n, m;
scanf("%d%d", &n, &m);
vector<vector<int>> a(n, vector<int>(m));
forn(i, n) forn(j, m){
scanf("%d", &a[i][j]);
--a[i][j];
}
vector<vector<int>> b(n, vector<int>(m));
forn(i, n) forn(j, m) b[i][a[i][j]] = j;
sort(b.begin(), b.end());
forn(i, n){
int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
int ans = 0;
if (j > 0) ans = max(ans, get(a[i], b[j - 1]));
if (j < n) ans = max(ans, get(a[i], b[j]));
printf("%d ", ans);
}
puts("");
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n;
li m1, m2;
inline bool read() {
if(!(cin >> n >> m1 >> m2))
return false;
return true;
}
vector<pt> mFact;
vector<li> divs;
void factM(li m1, li m2) {
mFact.clear();
for (int d = 2; d * d <= m1 || d * d <= m2; d++) {
int cnt = 0;
while (m1 % d == 0) {
m1 /= d;
cnt++;
}
while (m2 % d == 0) {
m2 /= d;
cnt++;
}
if (cnt > 0)
mFact.push_back({d, cnt});
}
if (m1 > m2)
swap(m1, m2);
if (m1 > 1)
mFact.push_back({m1, 1});
if (m2 > 1) {
if (m2 == m1)
mFact.back().y++;
else
mFact.push_back({m2, 1});
}
}
void genDivisors(int pos, li val) {
if (pos >= sz(mFact)) {
divs.push_back(val);
return;
}
li cur = val;
fore (pw, 0, mFact[pos].y + 1) {
genDivisors(pos + 1, cur);
if (pw < mFact[pos].y)
cur *= mFact[pos].x;
}
}
inline void solve() {
factM(m1, m2);
divs.clear();
genDivisors(0, 1);
sort(divs.begin(), divs.end());
vector<int> ans(sz(divs), 0);
vector<li> dp(sz(divs), -1);
fore (id, 0, sz(divs)) {
if (divs[id] <= n)
dp[id] = divs[id];
for (auto [p, pw] : mFact) {
if (divs[id] % p != 0)
continue;
int pos = int(lower_bound(divs.begin(), divs.end(), divs[id] / p) - divs.begin());
dp[id] = max(dp[id], dp[pos]);
}
if (divs[id] / dp[id] <= n)
ans[id] = divs[id] / dp[id];
}
int cnt = 0;
int xorSum = 0;
fore (i, 0, sz(ans)) {
cnt += ans[i] > 0;
xorSum ^= ans[i];
}
// cout << sz(ans) << endl;
// cout << ans << endl;
cout << cnt << " " << xorSum << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
1792F1 - Покраска графа (простая версия)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int varMul(int x)
{
return x;
}
template<typename... Args>
int varMul(int x, Args... args)
{
return mul(x, varMul(args...));
}
int binpow(int x, int y)
{
int z = 1;
while(y)
{
if(y & 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
vector<int> fact, rfact;
vector<int> dp;
int n;
void precalc()
{
fact.resize(n + 1);
rfact.resize(n + 1);
fact[0] = 1;
for(int i = 1; i <= n; i++)
fact[i] = mul(i, fact[i - 1]);
for(int i = 0; i <= n; i++)
rfact[i] = binpow(fact[i], MOD - 2);
dp.resize(n + 1, -1);
}
int C(int n, int k)
{
if(n < 0 || n < k || k < 0) return 0;
return varMul(fact[n], rfact[k], rfact[n - k]);
}
int calc(int x)
{
if(dp[x] != -1) return dp[x];
if(x == 1) return dp[x] = 1;
if(x == 2) return dp[x] = 1;
dp[x] = 0;
int& d = dp[x];
for(int i = 1; i < x; i++)
{
d = add(d, varMul(calc(i), (i == x - 1 ? (MOD + 1) / 2 : calc(x - i)), 2, C(x - 1, i - 1)));
}
return d;
}
int main()
{
cin >> n;
precalc();
cout << add(mul(calc(n), 2), -2) << endl;
}
1792F2 - Покраска графа (сложная версия)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int LOGN = 18;
const int N = (1 << LOGN);
const int MOD = 998244353;
const int g = 3;
#define forn(i, n) for(int i = 0; i < int(n); i++)
inline int mul(int a, int b)
{
return (a * 1ll * b) % MOD;
}
inline int norm(int a)
{
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
inline int binPow(int a, int k)
{
int ans = 1;
while(k > 0)
{
if(k & 1)
ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
inline int inv(int a)
{
return binPow(a, MOD - 2);
}
vector<int> w[LOGN];
vector<int> iw[LOGN];
vector<int> rv[LOGN];
void precalc()
{
int wb = binPow(g, (MOD - 1) / (1 << LOGN));
for(int st = 0; st < LOGN; st++)
{
w[st].assign(1 << st, 1);
iw[st].assign(1 << st, 1);
int bw = binPow(wb, 1 << (LOGN - st - 1));
int ibw = inv(bw);
int cw = 1;
int icw = 1;
for(int k = 0; k < (1 << st); k++)
{
w[st][k] = cw;
iw[st][k] = icw;
cw = mul(cw, bw);
icw = mul(icw, ibw);
}
rv[st].assign(1 << st, 0);
if(st == 0)
{
rv[st][0] = 0;
continue;
}
int h = (1 << (st - 1));
for(int k = 0; k < (1 << st); k++)
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
}
}
inline void fft(int a[N], int n, int ln, bool inverse)
{
for(int i = 0; i < n; i++)
{
int ni = rv[ln][i];
if(i < ni)
swap(a[i], a[ni]);
}
for(int st = 0; (1 << st) < n; st++)
{
int len = (1 << st);
for(int k = 0; k < n; k += (len << 1))
{
for(int pos = k; pos < k + len; pos++)
{
int l = a[pos];
int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
a[pos] = norm(l + r);
a[pos + len] = norm(l - r);
}
}
}
if(inverse)
{
int in = inv(n);
for(int i = 0; i < n; i++)
a[i] = mul(a[i], in);
}
}
int aa[N], bb[N], cc[N];
vector<int> multiply(vector<int> a, vector<int> b)
{
int sza = a.size();
int szb = b.size();
int n = 1, ln = 0;
while(n < (sza + szb))
n <<= 1, ln++;
for(int i = 0; i < n; i++)
aa[i] = (i < sza ? a[i] : 0);
for(int i = 0; i < n; i++)
bb[i] = (i < szb ? b[i] : 0);
fft(aa, n, ln, false);
fft(bb, n, ln, false);
for(int i = 0; i < n; i++)
cc[i] = mul(aa[i], bb[i]);
fft(cc, n, ln, true);
int szc = n;
vector<int> c(szc);
szc = n;
for(int i = 0; i < n; i++)
c[i] = cc[i];
return c;
}
int main()
{
int n;
cin >> n;
vector<int> fact(n + 1);
fact[0] = 1;
for(int i = 0; i < n; i++)
fact[i + 1] = mul(fact[i], i + 1);
precalc();
vector<int> A = {0, 1, 2};
vector<int> B = {0, 1, 1};
vector<int> C = {0, 1, 1};
vector<int> D = {0, 1, 1};
vector<int> conv;
const int K = 2000;
int last_conv = -1e9;
while(A.size() <= n)
{
int cur = A.size();
if(cur - last_conv >= K)
{
last_conv = cur - 1;
conv = multiply(C, D);
}
/*for(auto x : conv) cerr << x << " ";
cerr << endl;*/
int val_A;
if(last_conv * 2 >= cur)
{
val_A = conv[cur];
// [cur - last_conv, last_conv] are already used
for(int i = 1; i < (cur - last_conv); i++)
{
val_A = norm(val_A + mul(C[i], D[cur - i]));
}
for(int i = last_conv + 1; i < cur; i++)
{
val_A = norm(val_A + mul(C[i], D[cur - i]));
}
}
else
{
val_A = 0;
for(int i = 1; i <= cur - 1; i++)
{
val_A = norm(val_A + mul(C[i], D[cur - i]));
}
}
val_A = mul(val_A, fact[cur - 1]);
val_A = mul(val_A, 2);
A.push_back(val_A);
B.push_back(mul(val_A, inv(2)));
C.push_back(mul(val_A, inv(fact[cur])));
D.push_back(mul(B.back(), inv(fact[cur - 1])));
}
cout << norm(A[n] - 2) << endl;
}
Isn't it possible to have an O(n) solution for problem C (Min Max Sort)?
yeah, there's an easy $$$O(n)$$$ solution for problem C, involving using the array $$$pos[i]$$$, to get the position of index $$$i$$$ in the permutation, then start at the middle value and finding the $$$LIS$$$ to both side. My submission: 190340250
could you please explain it in a bit more detail thank you
nibba that was 2 ducking years ago, how tf am I supposed to remember that
lol
so basically think of it as a parenthesis
first we know that the best operation is to choose the ith element and the n-i th element
now let's mark them with their position and on a new array and sort them
now all you need to check is starting from the middle now you need to check upto what does the parenthessis extend
for 1 5 4 2 3 we have [1,0] , [2,3] , [3,4], [4,2] , [5,1]
now starting from the middle we check how many are already in place for us so we dont swap them just thinking of them like this will make thing this easier
(ik it's been 8 month ago)
I’ll go through it, thank you so much!!
sorry when i meant the ith element and the n-ith i meant when the array is sorted
like
1 2 3 4 5
1 and 5
2 and 4 e.t.c
maybe you read only the last line.
read the third last line.
Indeed I did. Thanks :)
can somebody explain how to come up with the equation in problem B.
Here, the Optimal strategy to solve the problem is by first saying all the jokes that both Alice and bob likes. (type 1 jokes) then by saying jokes alternately that (Alice likes,bob doesn't) and vice versa.
Final strategy is to say remaining jokes : first by saying remaining type 2, type 3 jokes and then by saying the jokes that both doesn't like (Type 4). this should be compared with the points that he already acquired hence a1 is taken. We take a1 + 1 as the judges goes when points become negative. Hence we add 1 to make it -1. Finally, We take the minimum of both these values to form the final equation.
Does anyone have an idea on proving the efficiency of bisearch-on-divisors approach for prob. E? Never expected it will be this fast = =
Can somebody explain what is the meaning of run binary search on k in problem C tutorial?
Remove value out of [k, n + k — 1] from array. If the remaining numbers are increasing （from [k, n + k — 1]), then the number k is appropriate.
You can use binary search to find k from [1, n].
You can see this submission, for more details:
https://mirror.codeforces.com/contest/1792/submission/190334713
For whatever it's worth, here's my $$$O(n \log n)$$$ solution for problem F.
First, we notice that the property for the set $$$S$$$ is the same as having a one-colored cut in $$$S$$$ (in other words, the set of vertices can be split into $$$S_1$$$ and $$$S_2$$$ so that all edges between $$$S_1$$$ and $$$S_2$$$ have the same color). The only issue is that a given set $$$S$$$ can possibly be split into $$$S_1$$$ and $$$S_2$$$ in several ways. So I introduce $$$f(n)$$$ to be equal to the number of graphs on $$$n$$$ vertices where the global cut is blue. Then the answer is $$$2 f(n) - 2$$$, since the global cut may be red, but $$$2$$$ extra cases arise when all edges have the same color.
To find $$$f(n)$$$ we need to partition the set of $$$n$$$ vertices into $$$k \geq 2$$$ subsets so that vertices from different subsets are connected by blue edges, but the subsets themselves obey the rules recursively (they have global cuts of red edges). Since $$$f_{\text{red}} = f_{\text{blue}}$$$, we have
where $$$C(a_1, \ldots, a_k)$$$ roughly means the number of ways to choose subsets of sizes $$$a_1, \ldots, a_k$$$ from a set of size $$$n = a_1 + \ldots + a_k$$$. If $$$b_1$$$ occurs $$$c_1$$$ times, $$$\ldots$$$, $$$b_m$$$ occurs $$$c_m$$$ times within the multiset $$${ a_1, \ldots, a_k}$$$, then
Define $h(n) = \frac{f(n)}{n!}.$ The base values are $$$h(0) = 0, h(1) = 1$$$. Via $$$H(x)$$$ we denote the generating function of $$$h$$$: $$$H(x) = h(0) + h(1) \cdot x + h(2) \cdot x^2 + \ldots$$$. After a careful examination (I don't know how to prove rigorously it though) we obtain
Everything else is the standard approach of how to solve these recurrences: if we know $$$H(x) \bmod{x^{m}}$$$, then from the equality above we can obtain $$$H(x) \bmod{x^{2m}}$$$. Underneath we need FFT (NTT) and an exponential generating function. Each step from $$$m$$$ to $$$2m$$$ takes $$$O(m \log m)$$$ time, so the overall complexity if $$$O(n \log n)$$$.
I also found this solution, thanks for sharing it!
I don't get why we have to make sure that no set of vertices is connected by both colors in F1. Doesn't the lemma proved it impossible to connect a set of vertices with both colors?
The lemma proves the other thing: it is impossible to have a set of vertices which is neither blue-connected nor red-connected.
Thanks. I made an oversight while reading the lemma.
A-F1 video editorial for Chinese:
BiliBili
In fact, we can calculate the convolution-like sequences (such as those in problem F) in $$$O(n \log^2 n)$$$ or $$$O(n \log^2 n / \log \log n)$$$ or even faster. One can find the approach from Elegia's report. The implementations usually has lower constant factor in time than those of the Newton iteration (if exist).
Here is my implementation, which imitates Elegia's implementations for other problems.
(but it's just as fast as a brute force lol)
Do you have this report as a PDF?
Here (sorry for Chinese only)
Do you know how to find ref. [5] (罗煜翔。(2020)。浅谈 Nimber 和多项式算法。IOI2020 中国国家集训队论⽂集。) ? I wanna see how to do semi-relaxed multiplication in $$$ \frac{n\log ^2 n}{\log \log n} $$$(if that's what it says). And what nimbers have to do with it xd.
Let's discuss about it here, actually in that report, most contents are just putting the general algorithm into the nimber framework. Nimber does not play an important role in the relaxed convolution.
"The array may large" in E made me realise how I don't trust my gut feeling at all.
Where does the log(divs(m)) of the complexity in question E come from Isn't it only need O(divs(m)⋅z(m)) to calculate the dp array?
oh i get it,because you can't find the element within O(1)
then why not use hash
constant factor is worse, I converted hash -> binary search + vector and it ran within time limit
can somebody explain why in D if we use lower_bound ans EITHER result or the previous one? why not just result? thanks in advance
It depends on the value immediately after the longest common prefix. While searching for $$$p$$$, you find some inverse $$$q_1, q_2, \dots, q_m$$$ that starts with $$$p_1, p_2, \dots, p_k$$$ for some $$$k$$$. The next value is different. If $$$q_{k+1} \gt p_{k+1}$$$, then lower_bound will point at $$$q$$$ (or one of inverses with such prefix if there are multiple). However, if $$$q_{k+1} \lt p_{k+1}$$$, then $$$q$$$ will be smaller than $$$p$$$, and lower_bound will jump over it. The next inverse has to be greater than $$$p$$$, so you only have to look one step behind.
For D, I thought while $$$n=5\times 10^4$$$, the number of subsets of $$$\{1,...,m\}$$$ is $$$10^3$$$.
So I constructed a map $$$M$$$ mapping each subset $$$L\subset \{1,...,m\}$$$ to $$$\{(a_i[p_1], ..., a_i[p_t])\ |\ i\in \{1,...,n\},\ \{p_1 \lt ... \lt p_t\}=L\}$$$. Then I iterated over every permutation and every $$$k$$$ to see whether the corresponding $$$k$$$ locations have the desired values.
For constructing $$$M$$$, it seemed that I can iterate over all subsets of $$$\{1,...,m\}$$$ and for each subset iterate over all permutations. This 2-layered loop is about $$$5\times 10^7$$$. But my actual implementation requires $$$O(2^m\times n\times m\times \log(n))\approx 8\times 10^9$$$ and thus got TLE. Not sure whether this is optimizable.
I thought of the same thing during the contest but midway realized that its gonna give TLE :(
Edit: This video has a similar approach
You can implement it with Trie in $$$O(2^m\times n \times m)$$$. I'm not sure whether it is fast enough.
It is not necessary to store all
2^msubsets. Let a permutation be3 2 4 1. For this we need to store0 0 0 1,0 2 0 1,3 2 0 1,3 2 4 1. So the complexity isO(n*m)Why don't we activate the numbers randomly, something like '0 2 0 0'?
I have some questions in problem F1
Why iterate k — the number of vertices whick are in the same 'red' component as 1 but not iterate the blue component, is this because you are counting the blue component?
What about the edges between vertices in the same componet as 1 and the rest vertices, are they must be the same color? how to proof?
Hope someone can help me, thx a lot
I understood!
Thanks a lot
Can someone give a test case on which my code is failing? I couldn't view the 156th item of 2nd test case. Is there any way to view it?
Click the "Click to see detail" button in the bottom of the page to see the detailed test cases
has anyone solved problem C with binary search ?
~~~~~
int l = -1; int r = n + 1; while(r - l > 1){ int m = (l+r) >>> 1; int min = m; int max = n - m + 1; List<Integer> list = new ArrayList<>(); for(int i = 0 ; i < n ; i++){ if(arr[i] > min && arr[i] < max){ list.add(arr[i]); } } boolean cc = true; for(int i = 0 ; i < list.size() - 1 ; i++){ int a = list.get(i); int b = list.get(i+1); if(a > b) cc = false; } if(cc) r = m; else l = m; } out.println(r);NEED PROVEMENT FOR PROBLEM F
Nevermind
F1's solution is flawed I guess. Consider case with n=3, when A1=B1=1, A2=2, B2=1, you get B3=4 which is incorrect.
So what's wrong with the $$$B_3=4$$$?
A3 which is the answer for n=3 is 6 in the pretest case, but surely 6 is not 4 * 2 :P
Well, maybe the tutorial forget something or i just didn't see.
But don't forget the limitation 1 and 2.
The $$$A_3=8$$$ contains the case that all blue and all red.
I noticed that too. I'm just saying that define "An" as "the answer for n" is not very strict and could lead to someone's misunderstanding(like me)
另外看兄弟id八成也是国人，直接说汉语就好了吧:)
哈哈
Sorry, I initially stated the problem without the constraints "at least one edge should be red" and "at least one edge should be blue". I wrote the editorial for that version, but then decided to introduce these constraints. So, the actual answer is $$$A_n-2$$$ since we need to discard the case "all edges are red" and the case "all edges are blue".
Time for problem E should be more strict. The following brute force solution passes:
Generate an array of increasing divisors. Make a copy and maintain it in
std::set<long long>. For each divisor $$$d_i$$$ in the original array, find the number of divisors that has $$$d_i$$$ as its first row, i.e. start fromdivs_set.lower_bound(d_i * d_i)and iterate until the value is greater than $$$d_i * n$$$, counting the number of divisors that are a multiple of $$$d_i$$$, and remove them from thesetafterwards.Can someone give some intuition why way 2 in E works
In editorial of problem E,it is mentioned that " There is also a way to get rid of extra log(divs(m)) factor if you iterate through dp in a smart way ".
How to do so? Could not find anything in comments and figure out neither.
is it possible to solve problem 'D' using trie?
Yes, it is
I just solved it using Trie: 251308798
you insert in the $$$trie$$$ the inverse of arrays $$$a_i$$$
and then for every array you look for the longest common prefix.
thanks
D can be solved with string hashing...
In the explanation for Problem C. It says in the third paragraph:
"There are several ways to check, let's consider one of them. Note that if the segment [k,n−k+1] is sorted for some value k, then it will be sorted for large values as well. So we can start with the maximum value of k (which is equal to ⌊n+12⌋) and decrease it until the segment remains sorted. Now for each k we need only two checks that posk < posk+1 and posn−k+1 > posn−(k+1)+1, where posi is the position of the element i in the permutation."
Note "until the segment remains sorted". I believe it should be "until the segment is no longer sorted"
because if it is not sorted for larger values of k i.e, a smaller, inner segment, then it is not sorted for smaller values of k a larger outer segment
e.g.
goal: 1 2 3 4 5 6
problem case: 2 3 1 6 4 5;
let p(x) be the position of x in the problem case Our max operations = n/2 -> 3
It works for p(3) < p(4), p(4) > p(3), max_op = 2 it works for p(2) < p(3), p(5) > p(4), max_op = 1 but p(1) < p(2) breaks hence, max_op remains 1
we need only one.
This was my implementation which you can find here in the
solve()function:https://mirror.codeforces.com/contest/1792/submission/348216142
can anyone explain why there is no comment on existence of an inverse for every q in the given set of permutations q, in question D? I know it is true because the multiplication is closed, associative and identity exists but is it required to mention in the solution or not?
A permutation is a bijection (i.e. it is one-to-one and onto) and so it must be invertible as all bijections have an inverse. I suppose the editorial solution takes this for granted and it might be worth mentioning, however, I assume this would be relatively common knowledge.
If you are interested in proving this yourself, the easiest proof off the top of my head would be showing every bijection has an inverse and that a permutation is a bijection.
(I understand this comment and editorial is quite old now but I'm just leaving this here for anyone else in the future who are curious about this)