提供一种直接基于期望推表达式的做法。
设 $p$ 表示走一步成功的概率，$E[x]$ 表示从一个存档点开始，还剩 $x$ 步的距离到达下一个存档点，所需的期望步数。若一次成功，共走 $x$ 步，概率为 $p^x$；若走到第 $i$ 步时失败，概率为 $p^{i-1}(1-p)$，之后需要重新开始，共走 $E[x]$ 步。因此有表达式：
直接将 $p = \frac{1}{2}$ 带入可知：
因此直接构造 $\texttt{100…}$ 的形式，类似二进制拆分进行构造即可。由于 $E[x]$ 为偶数，所以奇数的情况显然无解。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <bits/stdc++.h>
#define pii pair <int,int>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline ll read ();
void solve ()
{
ll x = read ();
if (x & 1) {puts ("-1");return;}
vector <ll> f (61,0);
for (int i = 0;i <= 60;++i) f[i] = (1ll << (i + 2)) - 2;
vector <int> ans;
for (int i = 60;~i;--i)
{
while (x >= f[i])
{
x -= f[i];
ans.push_back (1);
for (int j = 1;j <= i;++j) ans.push_back (0);
}
}
assert ((int)ans.size () <= 5000);
printf ("%d\n",(int) ans.size ());
for (auto v : ans) printf ("%d ",v);
puts ("");
}
int main ()
{
int t = read ();
while (t--) solve ();
return 0;
}
inline ll read ()
{
ll s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
