APIO2022 perm Sol

Erine · 2024-12-17 17:24:18 · 题解

呃为什么没有我这种做法。

考虑两个序列 a,b 拼接在一起。假设递增子序列数分别为 x,y。如果你让右边整体加，做到 \max\{a\}<\min\{b\}，子序列数会变成 xy。否则令左边整体加，会变成 x+y-1（-1 是因为空序列会被算两次）。

对于 k 很大的部分，暴力 pollard-rho 分解一下质因数，然后随便找一个接近 \sqrt k 的因数 p，从 p 和 \dfrac kp 合并过来。

对于 k\le 100 的部分，暴力枚举当前排列是怎么被拆成了两部分，更新一下。

大质数就寄了。所以 k 是质数的时候我们递归构造 k-1 的答案，然后全部抬高 1 后边再补一个 0 就好了。

不会算复杂度，但是跑的飞快，随了几个数答案也在 85 以内。

int dec(int n) {
    int B = min(n - 1, (int)sqrt(n) * 4), cur = 1;
    vector<int> d;
    while (n > 1) {
        int x = pr(n);
        d.push_back(x);
        n /= x;
    }
    if (n > 1) d.push_back(n);
    for (int i : d) if (i * cur <= B) cur *= i;
    return cur;
}

vector<int> f(int k) {
    if (k <= 100) return bk[k];
    vector<int> ans;
    if (mr(k)) {
        ans = f(k - 1);
        for (int &i : ans) ++i;
        ans.push_back(0);
    } else {
        int p = dec(k);
        ans = f(k / p);
        int x = ans.size();
        vector<int> r = f(p);
        for (int i : r) ans.push_back(i + x);
    }
    return ans;
}