İkili Əyləncə (Həll təhlili)

Həll

Bir ədəd $n$-ni bəzi "$k$-xüsusi" ədədlərin xor-u kimi ifadə etmək istəyirik. $k$-xüsusi ədəd, ikili formasında dəqiq $k$ ardıcıl $1$ olan və bütün digər bitləri $0$ olan hər hansı bir ədəddir, yəni

bəzi t \ge 0 sürüşməsi üçün. Başqa sözlə, bu, bitləri t, t+1, \dots, t+k-1 birlikdə dəyişir. Bizim əməliyyatımız xor-dur, beləliklə, eyni biti iki dəfə dəyişmək ləğv edir.

Əsas müşahidə budur ki, bu əməliyyat bitlərdə soldan sağa (əslində aşağıdan yuxarıya) bir istiqamətdədir. $n$-nin bitlərinə ən az əhəmiyyətli bitdən yuxarıya baxın. Tutaq ki, biz hazırda $i$ bitindəyik və bütün əvvəlki əməliyyatlardan sonra bitlər 0,1,\dots,i-1 artıq $0$ olub. Əgər $i$ biti $0$-dırsa, heç nə etməyə ehtiyac yoxdur. Əgər $i$ biti $1$-dirsə, $i$-də tam olaraq başlayan $k$-blokunu istifadə etməyə məcburuq:

• $i$-dən sonra başlayan hər hansı blok $i$ bitinə toxunmayacaq,

• $i$-dən əvvəl başlayan hər hansı blok $<i$ bitinə toxunacaq və artıq düzəltdiyimizi yenidən pozacaq,

beləliklə, $i$ bitini kiçik bitləri məhv etmədən təmizləməyin yeganə qanuni yolu xor etməkdir

Bunu etdikdən sonra, $i$ biti $0$ olur və i+1,\dots,i+k-1 bitləri dəyişir; sonra növbəti bitə keçirik.

Beləliklə, alqoritm tam olaraq belədir:

1. $n$-ni ikili formada yazın (saxlamaq üçün kifayət qədər $64$ bitdən az),

2. i=0,1,2,\dots üçün i+k \le 64 olduğu müddətcə:

   • əgər $i$ biti $1$-dirsə, onda $i$-də başlayan bloku götürün, cavaba əlavə edin və işçi nüsxəmizə xor edin,

3. bütün mümkün başlanğıcları etdikdən sonra, əgər yuxarıdakı (k-1) bitlərdə hər hansı bir $1$ qalıbsa, bu mümkün deyil (onu örtmək üçün kifayət qədər yüksək başlayacaq blok yoxdur), beləliklə cavab $-1$-dir,

4. əks halda, götürdüyümüz bloklar tam olaraq bir etibarlı quruluşdur.

Niyə bu minimaldır? Çünki hər dəfə $1$-lə rastlaşdığımızda seçimimiz yox idi: o $1$ orada məhv edilməlidir. Beləliklə, hər hansı bir həll o bloku ehtiva etməlidir. Hər seçilmiş blok məcbur olduğuna görə, hər hansı bir həll eyni blokların çoxluğuna malikdir $\Rightarrow$ beləliklə bu açgözlü minimal say verir və unikaldır.

Rəsmi olaraq, b_i-ni süzgəc zamanı bit $i$-nin cari dəyəri ilə təyin etsək, b_i=1 olan hər bir $i$ üçün biz əlavə edirik

quruluşa, və b_{i+j} \mathrel{\oplus}=1 edirik 0 \le j < k. Sonda əgər t > 64-k olan bəzi b_t=1 varsa, $-1$ çap edirik.

Komplekslik \mathcal{O}(\log^2 n)-dir.

def solve():
    n,k=map(int,input().split())
    b=n.bit_length()
    a=[]
    cur=0
    for i in range(b):
        bit=(n>>i)&1
        x=bit^cur
        a.append(x)
        cur^=x
        if i-k+1>=0:
            cur^=a[i-k+1]
    for j in range(1,k):
        if b-j>=0 and a[b-j]:
            print(-1)
            return
    base=(1<<k)-1
    v=[base<<i for i,x in enumerate(a) if x]
    print(len(v))
    print(*v)

for _ in range(int(input())):
    solve()