CF1859F Fancy Arrays-526互联

我们先找这题看起来有点奇怪的部分：
- \(x\leq 40\)
- \(|a_i-a_{i-1}|\leq k\)
我们先考虑第二个条件怎么用。我们发现 \(\min a_i \in [0,x+k)\)，而原数组相邻两数之差的条件肯定要考虑成差分来处理
可以发现，一个差分数组和 \(\min a_i\) 与一个 \(a_i\) 序列唯一对应。因为我们可以把差分求前缀和，然后找到里面的最小值，再整体加偏移量的方式得到 \(a_i\)
对于 \(\min a_i \in [x,x+k)\) 的情况自然不需要考虑，因为他们构造出来的一定都满足条件。而对于 \(\min a_i \in [0,x)\) 的情况，不满足条件当且仅当 \(\max a_i \in [0,x)\)，我们可以考虑容斥。
总方案：\((2k+1)^{n-1} \times (x+k)\)；现在我们即要求满足 \(a_i \in [0,x)\) 的 \(a_i\) 的方案数。我们可以 \(dp\) 来处理这个问题
设 \(dp_{i,j}\) 表示前 \(i\) 个数已经填好，第 \(i\) 个数填 \(j\) 的方案数。转移是 \(O(nk^2)\) 的，前缀和可以优化掉一个 \(k\)
发现 \(x \leq 40\)，于是矩阵快速幂优化 \(dp\)
最终复杂度 \(O(Tx^3\log n)\)