动态规划

题目分析 本题实际上要求的是满足以下条件的数组数量： 长度为给定值$n$； 每一个值都在限定范围$[l,r]$内； 相邻两个位置的关系从左到右依次增减交替变化。 基本思路 动态规划思路 由于本题要保证的只是数字的大小关系，并没有强制要求按照区间$[l,r]$进行计算，因此为了简便计算，可以将$l$和$r$都减少$l$，使区间变为$[0,r-l]$，这和原有情况是等价的。 本题要求最终的数组长度为$n$，如果此时确定第$n$个数字是$x$，并且确定最后两个数字呈上升趋势，那么就可以确定第$n-1$个数字的取值范围，这样，问题其实变成了一个相似但规模更小的问题。因此可以使用动态规划来解决该问题。仿照上面的分析，可以定义两个动态规划数组如下： $dp0[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈上升趋势的情况下，数组的总数量； $dp1[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈下降趋势的情况下，数组的总数量。 这样，答案就应该是$sum(dp0[n])+sum(dp1[n])$。 那么对于$dp0[i][j]$，由于最后两个数字呈上升趋势，因此可以确定第$i-1$个数字的取值范围为$[l,j-1]$，并且第$i-2$和第$i-1$个数字必须呈下降趋势，故可得递推公式如下： $$ dp0[i][j] = \sum_{k=l}^{j-1}dp1[i-1][k] $$类似的，对于$dp1[i][j]$，也可以得到递推公式如下： $$ dp1[i][j] = \sum_{k=j+1}^{r}dp0[i-1][k] $$根据上面两个公式，即可写出动态规划代码。观察到在递推关系式中用到了区间求和，因此可以用前缀和来优化，当加上前缀和优化时，本题目的第$I$题即可通过了。 矩阵乘法和快速幂优化 观察上面两个递推式子，不难发现，如果将$dp0[i]$和$dp1[i]$合并成一个长度为$2 \times (r-l+1)$的数组$dp[i]$，那么每一个$dp[i]$实际上都可以用同样一个公式从$dp[i-1]$中计算得来，而如果将$dp[i]$看作一个维度是$2 \times (r-l+1)$的空间中的一个坐标，那么上面说的这个递推公式其实可以看作一个坐标变换矩阵，每次只需用同样的矩阵乘以原来的坐标，即可得到新的坐标。 （注意，两个数组经过上述合并后，$dp0$中原有的索引不变，但$dp1$中原有的索引会增加$r-l+1$。为叙述方便，定义$k = r-l+1$） 举个例子，如果$k=2$，也就意味着数组中的每个位置上都只有两个数字可以选，那么根据之前的递推公式可以得到： $dp0[i][0] = 0$; $dp0[i][1]=dp1[i-1][0]$; $dp1[i][0]=dp0[i-1][1]$; $dp1[i][1] = 0$. 而如果将$dp0[i][x]$换成$dp[i][x]$，并将$dp1[i][x]$换成$dp[i][x+k]$，即可得到以下递推式： $dp[i][0] = 0$; $dp[i][1] = dp[i-1][2]$; $dp[i][2] = dp[i-1][1]$; $dp[i][3] = 0$; 因此可以整理出从$dp[i-1]$转成$dp[i]$所需要进行的坐标变换矩阵如下： $$ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $$总结规律，可以发现，对于任意一个$k$值，对应的坐标变换矩阵都可以按照下面方式列写： ...