Make SYSU Great Again IV
题目描述
对正整数序列 [w1,w2,…,wn](n≥3),考虑 n−1 个矩阵,其中第 i 个矩阵的大小为 wi×wi+1。
矩阵乘法顺序必须保持不变,但可以任意添加合法的括号。将一个 p×q 矩阵与一个 q×r 矩阵相乘,运算次数为 pqr。记所有合法加括号方案中,总运算次数的最小值为
MCOP([w1,w2,…,wn]).
给定整数 X,构造一个正整数序列 [a1,…,al],满足:
- 3≤l≤6;
- 1≤ai≤4000;
- MCOP([a1,…,al])=X。
可以证明,对范围内的每个 X 都存在合法构造。
输入格式
第一行一个整数 T,表示测试数据组数。
接下来 T 行,每行一个整数 X。
输出格式
每组数据输出两行:第一行输出序列长度 l,第二行输出 l 个整数 a1,…,al。
若有多个合法构造,可以输出任意一个。
数据范围
1≤T≤500,1≤X≤109。
样例
2
90
10
4
5 3 2 6
3
1 1 10
第一组中,两种加括号方案分别需要 5×3×2+5×2×6=90 次和 3×2×6+5×3×6=126 次运算,因此最小值是 90。