题目描述
https://codeforces.com/problemset/problem/1453/D
Solution
我们考虑 $100000$ 即 $1$ 后面跟着一堆 $0$ 的贡献
不妨假设有 $n - 1$ 个 $0$ 和 $1$ 个 $1$，我们有 $f[i]$ 表示从 $i$ 走到 $n$ 的期望次数
显然有 $f[n]=0$，然后我们有递推公式 $f[i]=\frac{1}{2}f[i+1]+\frac{1}{2}f[0]+1$
这个东西打表可以得到 $f[0]=2^{n+1}-2$
然后就可以愉快的构造了
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#define maxn 2010
#define maxm 100010
#define ll long long
#define pb push_back
#define cn const node
#define cQ const Queue
using namespace std;
ll n;
void work() {
cin >> n; vector<int> ans;
if (n & 1) return (void) (cout << "-1\n");
for (int i = 60; i >= 2; --i)
if (n >= (1ll << i) - 2) {
n -= (1ll << i) - 2;
ans.pb(1);
for (int j = 1; j < i - 1; ++j) ans.pb(0);
}
for (int i = 2; i <= n; i += 2) ans.pb(1);
cout << ans.size() << "\n";
for (auto u : ans) cout << u << " "; cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|