# Codeforces - 1166D - Cute Sequences

## 地址

http://codeforces.com/contest/1166/problem/D

## 原文地址

https://www.lucien.ink/archives/433

## 题目

Given a positive integer $m$, we say that a sequence $x_1, x_2, \dots, x_n$ of positive integers is $m$-cute if for every index $i$ such that $2 \le i \le n$ it holds that $x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$ for some positive integer $r_i$ satisfying $1 \le r_i \le m$.

You will be given $q$ queries consisting of three positive integers $a$, $b$ and $m$. For each query you must determine whether or not there exists an $m$-cute sequence whose first term is $a$ and whose last term is $b$. If such a sequence exists, you must additionally find an example of it.

## 题解

### 代码

https://pasteme.cn/8173

#include <bits/stdc++.h>
const int maxn = 54;
typedef long long ll;
ll __pow[maxn] = {1}, r[maxn], a, b, m;
int solve() {
if (a == b) return 1;
for (int n = 2; __pow[n - 2] <= b; n++) {
ll div = b / __pow[n - 2], mod = b % __pow[n - 2];
if (div > a && (div - a < m || (mod == 0 && div - a <= m)) && __pow[n - 2] - 1 >= mod) {
for (int i = 2, bit = n - 3; bit >= 0; i++, bit--) r[i] = (mod >> bit & 1) + div - a;
return n;
}
}
return -1;
}
ll calc(int x, int n) {
if (x > 1 && x < n) {
ll ret = __pow[x - 2] * a;
for (int i = 2; i < x; i++) ret = ret + __pow[x - i - 1] * r[i];
return ret + r[x];
} else return x == 1 ? a : b;
}
int main() {
int q, n;
for (int i = 1; i < maxn; i++) __pow[i] = __pow[i - 1] << 1;
for (scanf("%d", &q); q; q--) {
scanf("%lld%lld%lld", &a, &b, &m);
if (~(n = solve())) {
printf("%d ", n);
for (int i = 1; i <= n; i++) printf("%lld%c", calc(i, n), i == n ? '\n' : ' ');
} else puts("-1");
}
return 0;
}