Author: Copium

Ý tưởng:

Xét mảng $a[1\dots n]$ được xếp theo thứ tự không giảm $(a_1\le a_2\le \dots \le a_n)$, dễ thấy có $2^{i-1}$ subsequence nhận $a_i$ làm phần tử lớn nhất.

Vậy bài toán tương đương dựng mảng $a[1\dots n]$ sao cho :

• $a_i\le a_{i+1}$

• 

Vì mọi số $a_i$ có dạng $2^k$ đều thỏa mãn yêu cầu của đề bài, ý tưởng ở đây là ta sẽ sử dụng chúng để khôi phục lại biểu diễn nhị phân của số $x$.

Xét biểu diễn nhị phân của số $x$, gọi một bit là bật nếu như bit đó bằng $1$, ta dựng mảng $a[1\dots n]$ sao cho $n$ chính bằng số bit bật trong biểu diễn nhị phân của $x$ và mỗi phần tử $a_i$ sẽ tương đương với một bit bật.

Gọi $b_i$ là vị trí của bit thứ $i$ được bật từ bên phải sang, khi biết biểu diễn của số $x$ trong hệ nhị phân ta có thể tính giá trị của $x$ trong hệ thập phân bằng công thức sau :

Vậy ta sẽ dựng mảng $a[1\dots n]$ sao cho:

• $2^{i-1}\times a_i=2^{b_i}\leftrightarrow a_i=\frac{2^{b_i}}{2^{i-1}}=2^{b_i-(i-1)}$

Dễ thấy $b_i\ge (i-1)$ và $b_{i+1}-b_i\ge 1⟶a_i\ge a_{i+1}$ nên mảng $a[1\dots n]$ luôn thỏa mãn đề bài

Code mẫu

Copy

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = 2e5+5;
const int LOG = 20;
const int MOD = 998244353;
const ll INF = 1e15+5;

ll add(ll a, ll b) { return (a+b) % MOD; }
ll sub(ll a, ll b) { return (a-b+MOD) % MOD; }
ll mul(ll a, ll b) { return (a*b) % MOD; }

vector<ll> ans;

void solve(ll val) {
    ll contribution = 1;
    while(val > 0) {
        ll temp = val&(-val);
        ans.pb(temp/contribution);
        contribution *= 2;
        val -= temp;
    }

    cout << sz(ans) << "\n";
    foa(elem, ans) cout << elem << " ";
    cout << "\n";

    ans.clear();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
    int t;
    cin >> t;
    while(t--) {
        ll x;
        cin >> x;
        solve(x);
    }
}