Description：

每次把每个位置上的数变成这个位置的前缀和，问 $k$ 次操作之后每个位置上的值。

$1\leqslant n\leqslant 2000,1\leqslant k\leqslant 10^9$

Solution：

看数据范围不是矩乘就是倍增，矩乘的话转移矩阵就是： $$ \begin{bmatrix} 1&0&0&\cdots&0\\ 1&1&0&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&\cdots&0 \end{bmatrix} $$ 发现无论怎么乘一定都只有左下半部分有值，而且同一斜线上值相同，那么我们就可以只保存最左边一列的值，然后改写一下矩阵乘法也可以 $O(n^2)$ 转移，于是时间复杂度 $O(n^2\log n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 1000000007

int n,k;

#define MAXN 2010

int a[MAXN];

struct matrix

{

	int m[MAXN];

	matrix(){memset(m,0,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 1;i <= n;++i)

			for(int k = 1;k <= i;++k)

				c.m[i] = (c.m[i] + 1ll * a.m[i - k + 1] * b.m[k] % MOD) % MOD;

		return c;

	}

	friend matrix operator ^ (matrix a,int b)

	{

		matrix res = a;--b;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

}f;

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	if(k == 0)

	{

		for(int i = 1;i <= n;++i)printf("%d ",a[i]);

		puts("");

		return 0;

	}

	for(int i = 1;i <= n;++i)f.m[i] = 1;

	f = f ^ k;

	for(int i = 1;i <= n;++i)

	{

		int sum = 0;

		for(int j = 1;j <= i;++j)

		{

			sum = (sum + 1ll * f.m[i - j + 1] * a[j] % MOD) % MOD;

		}

		printf("%d ",sum);

	}

	puts("");

	return 0;

}