对a[1..n]进行"一次操作"是指令 新a[i]=sigma(k=1..i,原a[i]).
现在给出a[1..n]和k，求出a[]进行k次操作以后的结果。
n<=2000,k<=10^9.

明显可以用矩阵去想对吧? 然后就n^3logk，TLE。
注意到转移矩阵具有很好的性质：
a)只有主对角线(左上-右下)及其上的元素非0；
b)同一[左上-右下对角线]上的元素总相等。
c)具有上述性质的两个矩阵a和b相乘所得到的矩阵c也具有上述性质。
不妨假定行和列的标号都从0开始，重述上面的两条性质如下：
a)只有0<=i<=j<n时，a[i][j]非0；
b)如果0<=i<=j<=k<n且j-i=k-j，则a[i][j]=a[j][k]。
由b)可以马上得到a[i][j]=a[0][j-i]。
这意味着，有用的元素只有0行的n个元素——所以只用存下0行就可以了。
进一步地，计算矩阵乘法c=a*b时：
c[0][i]
=sigma(j=0..n-1)a[0][j]*b[j][i]
=sigma(j=0..i)a[0][j]*b[j][i] (性质a)
=sigma(j=0..i)a[0][j]*b[0][i-j] (性质b)
于是，矩阵被压缩成了一行，这个特殊情况下的矩乘也变成了n^2。
O(n^2logk)，可以接受。

似乎这题你会发现系数就是杨辉三角。。。然后就好搞了、