Fixed Prefix Permutations

Created by LXC on Fri Jun 2 10:11:40 2023

https://codeforces.com/problemset/problem/1792/D

ranting: 1700

tag: binary search, bitmasks, data structures, hashing, math, sortings

problem

给出n个排列，每个排列的长度为m（m<10）。

定义排列的乘法，排列a与排列b相乘得到排列r，即$a\cdot b= r$，其中$r_j = b_{a_{j}}$

定义排列的美丽值，当排列r的美丽值为k，那么$a_{1} = 1, a_{2} = 2, \cdots, a_{k} = k, a_{k+1} \ne k+1$。当$a_{1} \ne 1$时美丽值为0

现在需要输出当i在1到n时，$a_i\cdot a_j, (1\le j\le n)$的最大美丽值。

solution

由于$a_i\cdot a_j= r$，那么$a_i = r\cdot a_j^{-1}$。

当$r$的美丽值为$k$时，$a_i$与$a_j^{-1}$的前k个数是相等的。

我们可以先将每个排列的逆求出。然后存入能快速查询的数据结构——前缀树。对于每个$a_i$只需在前缀树中寻找最长前缀便是答案。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
#define MAXN 1000005
#define SIGMA 11
using namespace std;

struct Trie {
    int tr[MAXN][SIGMA];  // 数组存储Trie树节点,下标起到指针作用
    int sz;               // Trie中当前节点个数

    Trie() { init(); }
    void init() {
        memset(tr[0], 0, sizeof(tr[0]));
        sz = 1;
    }
    // 插入
    void insert(vector<int>& s) {
        int len = s.size(), u = 0;
        for (int i = 0; i < len; i++) {
            if (tr[u][s[i]] == 0) {  // 不存在新开就一个节点
                tr[u][s[i]] = sz;
                memset(tr[sz], 0, sizeof(tr[sz]));
                sz++;
            }
            u = tr[u][s[i]];
        }
    }
    int query(vector<int>& s) {
        int len = s.size(), u = 0;
        for (int i = 0; i < len; i++) {
            if (tr[u][s[i]] == 0)
                return i;
            u = tr[u][s[i]];
        }
        return len;
    }
};

int a[N][11];
Trie trie;

void sol() {
    trie.init();
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m, 0));
    for (auto& i : a) {
        for (auto& j : i)
            cin >> j, j--;
    }
    int ans = 0;
    for (auto& i : a) {
        vector<int> b(m);
        for (int j = 0; j < m; j++) {
            b[i[j]] = j;
        }
        trie.insert(b);
    }
    for (auto& i : a) {
        cout << trie.query(i) << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}