解説では添字は \(0\) から始まるものとします。

まず、 \(A\) の要素として \(2^{K-1}\) 未満の要素が入ることは無駄です。これは、 \(2^{K-1}\) 未満の要素を \(2\) 倍した要素に置き換えるとスコアの値は同じかそれ以上になることから従います。よって、 \(A\) の要素は全て \(2^{K-1}\) 以上 \(2^K\) 未満に限定して考えても良いです。

[1] \(N\geq 2^{K-1}\) の時

\(2^{K-1}\) 以上 \(2^K\) 未満の要素を全て \(A\) の中に含めることができるので、例えば \(A_i=\max(1,2^K-1-i)\) \((0\le i < N)\) とすれば良いです。

[2] \(N< 2^{K-1}\) の時

まず、スコアの上界を考えます。 \(0\le x < K\) に対し \(\displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor\) として現れる \(2^x\) 以上 \(2^{x+1}\) 未満の要素の個数を考えます。 すると、各 \(A_i\) に対し \(\displaystyle 2^x\le \left\lfloor\frac{A_i}{2^k} \right\rfloor < 2^{x+1}\) を満たす \(k\) は高々一つなので、この要素の個数は \(N\) 個以下であることが分かります。 一方で \(2^x\) 以上 \(2^{x+1}\) 未満の整数は \(2^x\) 個しかないので、結果として \(2^x\) 以上 \(2^{x+1}\) 未満の要素で現れる要素の個数は最大でも \(\min(N,2^x)\) 個であることが言えます。 よって、 \(x\) 全てに対する総和を取ることでスコアは \(\displaystyle 1 + \sum_{x=0}^{K-1}\min(N,2^x)\) を上界として持つことが分かりました。

この上界は必ず達成することができます。具体的には、 \(A\) を以下のように構成すれば良いです。

• \(A_i\) を \(i\) を bit-reversal したもの と\(2^{K-1}\) の和とする。

「 \(i\) を bit-reversal したもの」とは、\(i\) を \(K-1\) 桁の二進数表記したものを逆から見た時の値を指します。

例えば、 \(K=6,i=6\) なら \(i=00110_{(2)}\) なので \(i\) を bit-reversal したものは \(01100_{(2)}\) 、つまり \(12\) となります。

以上のことを実装することでこの問題に正解することができます。計算量は bit-reversal の計算がボトルネックとなり、 \(O(NK)\) となります。

実装例(Python3)

for _ in range(int(input())):
    N, K = map(int, input().split())

    def bit_reversal(x):
        return int(bin(x)[2:].zfill(K - 1)[::-1], 2)

    if N >= 2 ** (K - 1):
        print(*[max(1, 2**K - i - 1) for i in range(N)])
    else:
        print(*[2 ** (K - 1) + bit_reversal(i) for i in range(N)])

また、上界を達成するように上の bit から順番に構成していく方法でも正解することができます。詳しくは下の実装例を見てください。

実装例(Python3)

for _ in range(int(input())):
    N, K = map(int, input().split())
    C = [1]
    for _ in range(1, K):
        D = [2 * c for c in C] + [2 * c + 1 for c in C]
        C = D[:N]
    while len(C) < N:
        C.append(1)
    print(*C)