操作数解题报告

这一题确实有一定的思维难度

首先观察到k的范围，显然不能用朴素方法求解。

同时我们注意到每个数都等于它的前缀和

所以我们可以构造如下矩阵：

1 1 1 ... 1
0 1 1 ... 1
0 0 1 ... 1
...........
0 0 0 0...1

也就是说，我们只要让原数列 $[a_1,a_2,a_3,a_4,...,a_n]$ 乘上上面那个矩阵，就能得到 $s$ 序列

经过 $k$ 次操作之后就能得到结果

即我们要求的结果等于

$[a_1,a_2,a_3,a_4,\cdots,a_n] \times \left[ \matrix { 1 & 1 & 1 & \cdots & 1 \\ 0 & 1 & 1 & \cdots & 1 \\ 0 & 0 & 1 & \cdots & 1 \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & 0 & 0 & \cdots &1 }\right]^k$

然后怎么快速求的矩阵乘呢?

矩阵快速幂？ $N^3\log k$

复杂度承受不了

那么我们手推一下

假设是一个 $3 \times 3$ 的矩阵

就有

$\left[ \matrix { 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ }\right] \times\left[ \matrix { 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ }\right] =\left[ \matrix { 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \\ }\right]$

$\left[ \matrix { 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \\ }\right] \times\left[ \matrix { 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ }\right] =\left[ \matrix { 1 & 3 & 6 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \\ }\right]$

$\left[ \matrix { 1 & 3 & 6 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \\ }\right] \times\left[ \matrix { 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ }\right] =\left[ \matrix { 1 & 4 & 10 \\ 0 & 1 & 4 \\ 0 & 0 & 1 \\ }\right]$

怎么感觉哪里这么眼熟？

我们把杨辉三角写下来康康

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

注意到了吗？杨辉三角的第二列，第三列，第四列

前三个对应的就是结果矩阵的第一行

我们再看看 $4 \times 4$ 的

$\left[ \matrix { 1 & 2 & 3 & 4\\ 0 & 1 & 2 & 3\\ 0 & 0 & 1 & 2\\ 0 & 0 & 0 & 1\\ }\right] \times\left[ \matrix { 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\\ }\right] =\left[ \matrix { 1 & 3 & 6 & 10\\ 0 & 1 & 3 & 6\\ 0 & 0 & 1 & 3\\ 0 & 0 & 0 & 1\\ }\right]$

那么，我们就可以大胆的推测如下结论，初始矩阵的 $k$ 次对应的就是杨辉三角的第 $k$ 列的前 $n$ 个

然后我们知道杨辉三角是和组合数一一对应的，第 $i$ 行第 $j$ 个表示 $C_{i-1}^{j-1}$

但是这样做还是会有一个问题，就是在求组合数的时候复杂度会承受不了，而且分别求分子分母取模的做法会导致Wrong Answer

只要对杨辉三角有一定了解的同学就一定知道，第 $i$ 列的数字和从第 $i$ 行第一个向右下取得数字是一样的

那这个就可以很方便的求出来了， $C^m_n=\frac{n!}{m!(n-m)!}$ ,我们的 $n$ 和 $m$ 是同时增加的，所以 $(n-m)!$ 不变，只需要处理一下每一个位置对应的 $n$ 和 $m$ 即可

只要处理出第一行即可

操作数 解题报告

操作数解题报告