由于上一场 G 题没做出来。。打算重新复习一下各种排列相关的知识。。。

• 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

第一部分

错位排列（）

自反排列

• https://mathworld.wolfram.com/PermutationInvolution.html
• https://en.wikipedia.org/wiki/Involution_(mathematics)

交错排列

• http://oeis.org/A000111
• https://en.wikipedia.org/wiki/Euler_numbers

类 Catalan 递推公式

类 Pascal 递推公式

生成函数

• http://oeis.org/A008282

第二部分

循环分解

• https://www.shuizilong.com/house/archives/my_problems/

不动点

逆序对

#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;
	}
}

Posted by xiaodao
Category: 日常