D. Checkpoints

D题链接
题意：有n个点，每个点可以放1也可以不放1，某个人从1开始挑战，包括1，n都要挑战，挑战成功的概率和失败概率一样都是1/2，如果失败了就会回到离i这个点最近的1的点，问最后通关(挑战成功n）的期望步数。
思路:概率论纯属没有学好，看了题解期望原来是有可加性的，对于任意$100000..$这样的序列，可以构成一个关卡，最后期望就是E的总和。然后我们计算子关卡的期望步数，$$E[i]=E[i-1]+1+1/2\ast E[i]+1/2\ast 0$$$E[i]$代表挑战完第i个关卡需要的期望，那么就是个简单的期望dp罢了，$E[i-1]$走完以后，下一步有两种可以，一种挑战成功到达$E[i-1]$，另一种回到初始点，还需要走$E[i]$步,然后移项$E[i]=2\ast E[i-1]+2$ 那么就是通项求和就是$2^n\ast 2-2$那么最后输出一种方案，众所周知，和肯定是偶数，奇数直接无解，偶数从最大的$2^n\ast 2-2$开始构造就行了。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug printf("---\n");
const int N=210,M=10010;
int main()
{
   
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
   
		ll k;
		cin>>k;
		if(k&1)
		{
   
			cout<<"-1"<<endl;
			continue;
		}
		vector<ll>res;
		int tmp=0;
		while(k)
		{
   
			int n=1;
			while(true)
			{
   
				if(( (1ll<<(n+1))-2)>k)
				break;
			  	n++;
			}
		// cout<<k<<" "<<n<<endl;
			n--;
			res.push_back(n);
			tmp+=n;
			//cout<<k<<endl;
			k-=(1ll<<(n+1))-2;
		}
		cout<<tmp<<endl;
		for(auto x:res)
		{
   
			cout<<1<<" ";
			x--;
			while(x--)
			cout<<0<<" "; 
		}
		cout<<endl;
	}
	return 0;
}