Бінарні забави#12272

Бінарні забави (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редагував:	Хасан Салех (MathModel)

Рішення

Ми хочемо виразити число $n$ як XOR деяких " $k$ -спеціальних" чисел. $k$ -спеціальне число - це будь-яке число, бінарна форма якого має точно $k$ послідовних $1$ 's, а всі інші біти $0$ , тобто

x = ((1 ≪ k) - 1) ≪ t

x = \bigl((1 \ll k) - 1\bigr) \ll t

для деякого зсуву $t \geq 0$ t \ge 0. Іншими словами, воно переключає біти $t, t + 1, \dots, t + k - 1$ t, t+1, \dots, t+k-1 разом. Наша операція - XOR, тому переключення одного і того ж біта двічі скасовує.

Головне спостереження полягає в тому, що ця операція є односторонньою для бітів зліва направо (насправді з низу вгору). Подивіться на біти $n$ з найменш значущого біта вгору. Припустимо, що ми зараз на біті $i$ , і після всіх попередніх операцій біти $0, 1, \dots, i - 1$ 0,1,\dots,i-1 вже стали $0$ . Якщо біт $i$ є $0$ , нам не потрібно нічого робити. Якщо біт $i$ є $1$ , ми змушені використовувати $k$ -блок, який починається точно на $i$ :

будь-який блок, який починається після $i$ , не торкнеться біта $i$ взагалі,
будь-який блок, який починається до $i$ , торкнеться деякого біта $< i$ і знову зламає те, що ми вже виправили,

тому єдиний законний спосіб очистити біт $i$ , не знищуючи менші біти, - це XOR

((1 ≪ k) - 1) ≪ i .

\bigl((1 \ll k) - 1\bigr) \ll i.

Після того, як ми це зробимо, біт $i$ стає $0$ , а біти $i + 1, \dots, i + k - 1$ i+1,\dots,i+k-1 переключаються; потім ми переходимо до наступного біта.

Отже, алгоритм буквально такий:

запишіть $n$ у двійковому вигляді (досить, щоб зберегти $\leq 64$ біт),
для $i = 0, 1, 2, \dots$ i=0,1,2,\dots поки $i + k \leq 64$ i+k \le 64:
- якщо біт $i$ є $1$ , то візьміть блок, що починається на $i$ , додайте його до відповіді та XOR-те його в нашу робочу копію,
після того, як ми зробили всі можливі початки, якщо залишився будь-який $1$ у верхніх $(k - 1)$ (k-1) бітах, то це неможливо (немає блоку, який може початися досить високо, щоб його покрити), тому відповідь - $- 1$ ,
в іншому випадку обрані блоки є точною однією дійсною конструкцією.

Чому це мінімально? Тому що щоразу, коли ми зустрічали $1$ , у нас не було вибору: цей $1$ повинен бути знищений прямо там. Тому будь-яке рішення повинно містити цей блок. Оскільки кожен обраний блок є примусовим, будь-яке рішення має однаковий мультисет блоків $\Rightarrow$ отже, цей жадібний алгоритм дає мінімальну кількість і є унікальним.

Формально, якщо ми позначимо $b_{i}$ b_i як поточне значення біта $i$ під час проходження, то для кожного $i$ з $b_{i} = 1$ b_i=1 ми додаємо

x_{i} = ((1 ≪ k) - 1) ≪ i

x_i = \bigl((1 \ll k) - 1\bigr) \ll i

до конструкції і робимо $b_{i + j} \oplus = 1$ b_{i+j} \mathrel{\oplus}=1 для $0 \leq j < k$ 0 \le j < k. В кінці, якщо деяке $b_{t} = 1$ b_t=1 з $t > 64 - k$ t > 64-k, тоді ми виводимо $- 1$ .

Складність становить $O (lo g^{2} n)$ \mathcal{O}(\log^2 n).

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()

Python