题目大意

给定数组 $a$ ，每次变换将 $a_i$ 变换为 $a$ 中 $a_i$ 出现的次数。询问 $k$ 次变换后 $a_x$ 的值。

$e.g.$

$$\begin{aligned} &\text{初始数组} &2 \ 1 \ 1 \ 4 \ 3 \ 1 \ 2 \\ &\text{第一次变换后} & 2 \ 3 \ 3 \ 1 \ 1 \ 3 \ 2 \\ &\text{第二次变换后} & 2 \ 3 \ 3 \ 2 \ 2 \ 3 \ 2 \\ &\text{第二次变换后} & 4 \ 3 \ 3 \ 4 \ 4 \ 3 \ 4 \\ &\dots &\dots \\ \end{aligned} $$

分析

我们称 $a$ 中所有相同的元素为一组。

容易发现，当一组内的元素等于其出现次数时，这组元素便不再变化。我们称这种状态为稳定。

所以说，当没有组发生合并，也就是所有元素都不发生变化时，以后也不会再有变化。此时整个数组稳定。

换言之，在整个数组稳定前，组的数量严格递减。

很容易得出最多变换 $n$ 次整个数组便稳定的结论。

（官方题解说最多 $\log n$ 次就会达到稳定，可是我不会证。不过 $n$ 次的复杂度也足够通过此题了。）

代码

#include <cstdio>
#include <iostream>

const int MAX_N = 2050;

int a[MAX_N][MAX_N];

template <typename T>
T read();

int main() {
    std::ios::sync_with_stdio(false);

    int T = read<int>();
    while (T--) {
        int n = read<int>();

        for (int i = 1; i <= n; i++) {
            a[0][i] = read<int>();
        }
        for (int i = 1; i <= n; i++) {
            auto *cnt = new int[n + 1]{};
            for (int j = 1; j <= n; j++) {
                cnt[a[i - 1][j]]++;
            }
            for (int j = 1; j <= n; j++) {
                a[i][j] = cnt[a[i - 1][j]];
            }
        }

        int q = read<int>();
        while (q--) {
            int x = read<int>(), y = read<int>();
            std::cout << a[std::min(y, n)][x] << '\n';
        }
    }

    return 0;
}

template <typename T>
T read() {
    T x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}