第3题

long long k;
int n;
int p[20];
bool used[20] = {false};
long long frac[20];

void gen(int i)
{
    if (i > n)
    {
        for (int i = 1; i <= n; ++i) std::cout << p[i] << " ";
        return;
    }

    for (int a = 1; a <= n; ++a)
        if (not used[a]) {
            if (k <= frac[n-i]) {
                p[i] = a;
                used[a] = true;
                gen(i+1);
                return;
            }
            else {
                k -= frac[n-i];
            }
        }
}

int main()
{
    n = 1;
    frac[0] = frac[1] = 1;
    std::cin >> k;
    while (k > frac[n]) {
        k -= frac[n];
        frac[n+1] = frac[n] * (n+1);
        n++;
    }
    gen(1);
}

下列说法正确的是（ ）。

{{ select(1) }}

• 越大的 $k$ 一定会输出越长的序列
• $k$ 若是奇数，输出序列的长度一定也是奇数
• 程序的时间复杂度为 $\Theta(k!)$
• gen 递归是树形递归