#P17924. Make SYSU Great Again IV

Make SYSU Great Again IV

Make SYSU Great Again IV

题目描述

对正整数序列 [w1,w2,…,wn][w_1,w_2,\ldots,w_n](n≥3n\ge3),考虑 n−1n-1 个矩阵,其中第 ii 个矩阵的大小为 wi×wi+1w_i\times w_{i+1}。

矩阵乘法顺序必须保持不变,但可以任意添加合法的括号。将一个 p×qp\times q 矩阵与一个 q×rq\times r 矩阵相乘,运算次数为 pqrpqr。记所有合法加括号方案中,总运算次数的最小值为

MCOP⁡([w1,w2,…,wn]).\operatorname{MCOP}([w_1,w_2,\ldots,w_n]).

给定整数 XX,构造一个正整数序列 [a1,…,al][a_1,\ldots,a_l],满足:

  • 3≤l≤63\le l\le6;
  • 1≤ai≤40001\le a_i\le4000;
  • MCOP⁡([a1,…,al])=X\operatorname{MCOP}([a_1,\ldots,a_l])=X。

可以证明,对范围内的每个 XX 都存在合法构造。

输入格式

第一行一个整数 TT,表示测试数据组数。

接下来 TT 行,每行一个整数 XX。

输出格式

每组数据输出两行:第一行输出序列长度 ll,第二行输出 ll 个整数 a1,…,ala_1,\ldots,a_l。

若有多个合法构造,可以输出任意一个。

数据范围

1≤T≤5001\le T\le500,1≤X≤1091\le X\le10^9。

样例

2
90
10
4
5 3 2 6
3
1 1 10

第一组中,两种加括号方案分别需要 5×3×2+5×2×6=905\times3\times2+5\times2\times6=90 次和 3×2×6+5×3×6=1263\times2\times6+5\times3\times6=126 次运算,因此最小值是 9090。