[数据结构与算法]牛客数据结构专题班WeekⅠ 前缀和练习

前缀和，狭义的理解是$$f[n]=\sum _{i=1}^{n}g[i]$$这样一个把前面所有的值都加起来的一种操作，方便区间和进行查询，但是通过进一步的了解，前缀和可以用来表示前面的操作都进行完，之后通过某种操作消除前面某一段的影响，进而求得某段区间操作之后的总影响。

这样干说似乎有点抽象，借助第一场的几个题来进一步讲一下，也当作改题的一篇blog吧
AC个数：9/10
传送门
过于简单的就不写了，反正我会的我队友肯定都会

1. 矩阵乘法优化dp(在数据结构课上你甚至可以写dp )
   题意
   我们首先考虑如果这是一道dp，不是那么多次询问怎么做呢？
   很容易得出以下的状态转移方程：
   $$\begin{gathered} dp[i][0]=dp[i?1][0]+dp[i?1][1] \\ dp[i][1]=dp[i?1][1]+dp[i?1][0] \end{gathered}$$
   如果有一种从左面的楼到右面的楼的楼梯，那么第一个式子的后一项就有，第二个式子同理，但这题有多组询问，我们观察上面的状态转移方程：这个是一个矩阵的形式：如果有一个从左到右的楼梯的话，可以化成以下的矩阵
   $$\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]$$
   同理，如果存在一个从右到左的楼梯，那么可以化成以下的矩阵
   $$\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$$其中，这里的矩阵每个元素代表的意思分别为$$\begin{gathered} f[0][0]代表从左面到左面 \\ f[0][1]代表从左面到右面 \\ f[1][0]代表从左面到右面 \\ f[1][1]代表从右面到右面 \end{gathered}$$
   的方案数。之后可以利用前缀和的思想，把每个询问变成l逆矩阵乘以r的状态即可。
   代码如下：
   代码

2.前缀和的trick应用
题目：传送门
这个题看起来和前缀和没有任何关系，但是我们换一种想法，你对于l,r的操作，其实就是
让前l次操作变成0-9，这就是相当于一个映射，代码如下：
代码

3.前缀和与数学的结合：
前置数学知识点：最高次项为n次的多项式进行n+1次差分之后值为常数。
题目：传送门
如果暴力加入会必然超时的，但如果我们做差分，通过差分数组相加，那么时间将会非常优秀。代码如下：
代码
注意最后前缀和相减的时候需要注意一下矩阵乘法的顺序。

4.前缀和的数学贡献推导：
挖坑，yh给我讲完正解了，但实现得用NTT，学完NTT来补这道题呜呜