试证明，对于任一n×n的整数矩阵M，若首先对每一列分别排序，则继续对每一行分别排序后，其中的各列

设B为A=(1，2，3，...，n)的任一排列。

a)试证明，B是A的一个栈混洗，当且仅当对于任意1≤i＜j＜k≤n，P中都不含如下模式：{...，k，...，i，...，j，...}

b)若对任意1≤i＜j＜k＜n，B中都不含模式{...，j+1，...，i，...，j，...}，则B是否必为A的一个栈混洗？若是，试给出证明;否则，试举一反例。

c)若对任意1＜i＜j＜k≤n，B中都不含模式{...，k，...，j-1，...，j，...}，则B是否必为A的一个栈混洗？若是，试给出证明;否则，试举一反例。

令V=M_n(C)是复数域上全体n阶矩阵所组成的n²维向量空间，令A是任意一个n阶复矩阵。如下地定义V的一个线性变换α_A：V→V：对于任意X∈V=M_n(C)，α_A(X)=AX-AX。

(i)证明，r是非负整数，由此推出，如果A是幂零矩阵，那么α_A是V的幂零变换;

(ii)如果A=D+N是A的若尔当分解，其中D是A的可对角化部分，N是幂零部分，那么α_D和α_N分别是线性变换α_A的若尔当分解。

设使用Pratt序列：

对长度为n的任一向量S做希尔排序。

试证明：

a)若S已是(2，3)-有序，则只需o(n)时间即可使之完全有序;

b)对任何，若S已是(2h_k，3h_k)-有序，则只需o(n)时间即可使之h_k-有序;

c)针对序列中的前o(log^tn)项，希尔排序算法需要分别迭代一轮;

d)总体的时间复杂度为o(log²n)。

算法设计:对于给定的n个正整数,设计一个优先队列式分支限界法,用最少的无优先级运算次数产生整数m.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.第2行是给定的用于运算的n个正整数.

结果输出:将计算的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出到文件output.txt.