Codeforces Round #688 (Div. 2) D Checkpoints

n个数(一个 1 和 n-1 个 0)的期望:
P_n= P_n-1+ 2ⁿ
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll inf = 1e18;
 5 ll n,k,t;
 6 ll A[100],ans,cnt,p;
 7 int f[2007],cf;
 8 void cal(ll x){
 9     int lo=upper_bound(A+1,A+1+cnt,x)-A-1;    
10     x-=A[lo];
11     ans=ans+lo;
12     f[++cf]=lo;
13     if(x){
14         cal(x);
15     }
16 }
17 int main(){
18     std::ios::sync_with_stdio(false);
19     cnt=0,p=1;
20     A[0]=0;
21     for(cnt=1;;++cnt){
22         p=p*2;
23         A[cnt]=A[cnt-1]+p;
24         if(A[cnt]>inf) break; 
25     }
26     cin>>t;
27     while(t--){
28         ans=0,cf=0;
29         cin>>n;
30         if(n&1){
31             printf("-1
");
32             continue;
33         }
34         cal(n);
35         printf("%lld
",ans);
36         for(int i=1;i<=cf;++i){
37             printf("1 ");
38             for(int j=1;j<=f[i]-1;++j){
39                 printf("0 ");
40             }
41         }
42         printf("
");
43     }
44     return 0;
45 }