题解 | #Checkpoints#

【Checkpoints】

定义$\mathbb{E}(i)\backslash mathbb\{E\}(i)$为从第$ii$关开始到通关，所需要通过的关卡的期望。

假设从第 $ll$ 关开始到第 $rr$ 关只有第 $ll$ 关有存档点，那么：

由数学归纳法可得（令$L=r-l\ge 1L=r-l\backslash ge1$）:

因为$\mathbb{E}(n+1)=0\backslash mathbb\{E\}(n+1)=0$（通关），且任意项的$2^{L+1}-22^\{L+1\}-2$（$L\ge 1L\backslash ge\; 1$）相加均为偶数，所以$\mathbb{E}(1)\backslash mathbb\{E\}(1)$为偶数，即当$kk$为奇数时，一定构造不出来。

又因$(2^{L+1}-2)+(2^{1+1}-2)=2^{L+1}(2^\{L+1\}-2)+(2^\{1+1\}-2)=2^\{L+1\}$（$L\ge 1L\backslash ge\; 1$），多个$2^{L+1}2^\{L+1\}$（$L\ge 1L\backslash ge\; 1$）的累加可以表示任意偶数，故偶数一定可以构造出来。（$L=1,2^{1+1}-2=2L=1,\backslash \; 2^\{1+1\}-2=2$）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll k, T;
vector<int> res;
void solve() {
    res.push_back(1);
    if((1LL << 1) & k) res.push_back(1);
    for(int i = 2; i <= 60; i++) {
        if((1LL << i) & k) {
            for(int j = 1; j <= i - 2; j++) 
                res.push_back(0);
            res.push_back(1);
            res.push_back(1);
        }
    }
    
}

int main() {
    cin >> T;
    while(T--) {
        cin >> k;
        if(k & 1) {
            cout << -1 << "\n";
            continue;
        }
        res.clear();
        solve();
        cout << res.size() - 1 << "\n";
        for(int i = 0; i < res.size() - 1; i++) 
            cout << res[i] << " \n"[i == res.size() - 2];
    }
    return 0;
}