Description
给定一个正整数$m$，定义一个正整数序列$x_1,x_2,x_3,…,x_n$，满足对于$2\le i\le n$有$x_i=x_{i-1}+x_{i-2}+…+x_1+r_i$，其中$1\le r_i\le m$
现在给出$q$个询问，每个询问给出$a,b,m$，强制要求$x_1=a$，$x_n=b$，要求构造出一个长度不超过$50$的$x$序列
Input
第一行一个正整数$q(1\le q\le 10^3)$表示询问数
接下来$q$行，每行三个正整数$a,b,m(1\le a,b,m\le 10^{14},a\le b)$，意义见题面
Output
没有合法序列输出$-1$
有合法序列则先输出序列长度$k(k\le 50)$，然后$k$个数$x_1,x_2,…,x_k(1\le x_i\le 10^{14})$，其中$x_1=a,x_k=b$
Sample Input
1 | 2 |
Sample Output
1 | 4 5 6 13 26 |
Solution
又被sb题整弱智了.jpg
很容易推出$b=2^{k-2}\cdot a+2^{k-3}\cdot r_2+…+2^{k-i-1}\cdot r_i+…+r_{k-1}+r_k$
首先特殊情况是$a=b$，这时候直接输出$1\;a$
考虑到$k$很小，先枚举长度$k$
这时候$a$是确定的，因此可以先把$a$的部分减掉，同时把每个$r_i$都减$1$，这样来保证求出的$r_i$都是$\ge0$的，那么此时$0\le r_i\le m-1$
定义$cha=n-2^{k-2}\cdot a-2^{k-2}$
从$r_2$到$r_{k-1}$贪心考虑，系数大的尽量大，同时要注意不能超过$m-1$
这样构造出来，最后剩余的$r_k=cha$如果在$m$以内，就是合法的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
54
typedef long long ll;
const int N = 6e2 + 5, INF = 0x3f3f3f3f, mod = 998244353;
using namespace std;
namespace fast_IO {
inl ll read() {
rg char c;
rg ll x = 0;
rg bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == EOF)return c; if (c == '-')flag = true; else x = c ^ 48;
while ((c = getchar()) != ' ' && c != '\n' && c != '\r' && ~c)
x = (x << 1) + (x << 3) + (c ^ 48);
if (flag)return -x; return x;
}
inl ll max(rg ll a, rg ll b) { if (a > b)return a; return b; }
inl ll min(rg ll a, rg ll b) { if (a < b)return a; return b; }
void write(rg ll x) { if (x < 0)putchar('-'), x = -x; if (x >= 10)write(x / 10); putchar(x % 10 ^ 48); }
}
ll r[N];
int main(void) {
rg int q = fast_IO::read();
while (q--) {
rg ll a = fast_IO::read(), b = fast_IO::read(), m = fast_IO::read();
if (a == b) { printf("1 %I64d\n", a); continue; }
rg bool can = false; r[1] = a; rg int len;
for (rg int k = 2; k <= 50 && !can; ++k) {
rg ll cha = b - a * (1ll << k - 2) - (1ll << k - 2);
if (cha < 0)break;
for (rg int i = 2; i < k; ++i)
r[i] = fast_IO::min(m - 1, cha / (1ll << k - i - 1)), cha -= r[i] * (1ll << k - i - 1);
if (cha < m) {
can = true, len = k, r[len] = cha;
break;
}
}
if (!can)puts("-1");
else {
rg ll sum = a;
for (rg int i = 2; i <= len; ++i)++r[i], r[i] += sum, sum += r[i];
fast_IO::write(len);
for (rg int i = 1; i <= len; ++i)putchar(' '), fast_IO::write(r[i]);
putchar('\n');
}
}
return 0;
}