# 某岛

… : "…アッカリ～ン . .. . " .. .
November 14, 2022

## Permutation

• Combinatorial Problems and Exercises, 2nd Edition, László Lovász, #3 Permutations
• The Art of Computer Programming, Vol. 3 Sorting and Searching, 2nd Edition, Donald E. Knuth, 5.1. Combinatorial Properties of Permutations

# 第二部分

## 逆序对

#include <lastweapon/io>
#include <lastweapon/number>
using namespace lastweapon;

const int N = int(1e3) + 9;

int a[N], mx[N], mn[N], cc[N];
int n;

VI circle() {
bool static used[N]; RST(used);
VI z;
REP(i, n) if (!used[i]) {
int x = i; used[x] = true; int c = 1;
while (!used[a[x]-1]) {
x = a[x]-1;
used[x] = true;
++c;
}
z.PB(c);
}
return z;
}

bool used[N];

void dfs(int k = 0) {

if (k == n) {
//REP(i, n) cout << a[i] << " "; cout << endl;
VI r = circle();
++mx[*max_element(ALL(r))];
++mn[*min_element(ALL(r))];
++cc[SZ(r)];
} else {
REP_1(i, n) if (!used[i]) {
used[a[k] = i] = true;
dfs(k+1);
used[i] = false;
}
}
}

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

//scanf("%d%d",&n,&MOD);
REP_1(i, 10) {
//RD(n);

RST(used); RST(mn); RST(mx); RST(cc);
n = i; dfs();
//REP_1(i, n) cout << mx[i] <<" "; cout << endl;
//REP_1(i, n) cout << mn[i] <<" "; cout << endl;
REP_1(i, n) cout << cc[i] <<" "; cout << endl;
}
}