康托展开和逆康托展开

康托展开

//康托展开
constexpr int M = 998244353;
template<class T>
struct Fenwick {
    //比如说数组长度为5
    //-----------------a[3]
    //------a[1]
    //--a[0]    --a[3]     --a[4]
    //    1    2    3    4    5
    //add(x)修改的是x+1
    //sum(x)查询的是x
    int n;
    std::vector<T>a;
    Fenwick(int n_=0) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    void add(int x, const T& v) {

        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    T sum(int x) {
        T ans{};
        
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};

struct cantor {
    int n;
    std::vector<ll>fac;
    Fenwick<ll> f;
    cantor(int n_) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        fac.assign(n, 0);
        f.init(n);
        fac[0] = 1;
        for (int i = 1; i < n; i++) {
            fac[i] = i*fac[i - 1] % M;
        }
        for (int i = 0; i < n; i++) {
            f.add(i, 1);
        }
    }
    ll query(int x, std::vector<ll>a) {
        //树状数组求逆序对不就是
        ll sum = 0;
        for (int i = 0; i < x; i++) {
            sum = (sum + fac[n - i - 1] * f.sum(a[i]-1) % M) % M;
            f.add(a[i] - 1, -1);
        }
        return (sum+1) % M;
    }
};

void solve() {
    int n;
    std::cin >> n;
    cantor c(n);
    std::vector<ll>a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];

    }
    std::cout << c.query(n, a) << "\n";
}

逆康托展开

std::string invcantor(int n, ll k) {
    // 计算阶乘
    std::vector<ll> fac(n, 1);
    for (int i = 1; i < n; i++) {
        fac[i] = fac[i - 1] * i;
    }

    // 初始化未使用的数字集合
    std::vector<int> vis(n);
    std::iota(vis.begin(), vis.end(), 1);

    // 调整 k 为从 0 开始的索引
    k--;

    std::string ans;
    for (int i = 0; i < n; i++) {
        ll fact = fac[n - i - 1];
        int pos = k / fact; // 当前位数字的索引
        ans.push_back(vis[pos]+'0');
        vis.erase(vis.begin() + pos); // 从集合中移除已选数字
        k %= fact; // 更新 k
    }

    return ans;
}

原文地址：https://blog.csdn.net/Colinnian/article/details/144359037

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！