题目大意：
设一个长度为 \(n\) 的数组是 “Fancy” 的，当且仅当它满足下面条件。
- \(|a_{i} - a_{i - 1}| \le k\)
- 存在 \(i\) 满足 \(x \le a_{i} \le x + k - 1\)
- \(a_{i} \ge 0\)
给定 \(n,k,x\)，求 "Fancy" 的数量。
\(n,k \le 10^9 x \le 40\)
解题思路：
套路地，看到“存在”，想到“全部”减去“没有”，但这个题是行不通的，因为全部和没有都是 inf。
因为 \(x \sim x + k - 1\) 的范围足够大，所以当 \(\min(a_{i}) < x\) 且 \(\max(a_{i}) > x + k - 1\) 时一定会经过 \(x \sim x + k - 1\)。
也就是满足条件二当且仅当 \(min(a_{i}) \le x + k - 1\) 且 \(x \le max(a_{i})\)。
考虑第二个条件是不好做的，而且 \(x > max(a_{i})\) 范围相对小，考虑容斥，可以通过矩乘解决。
而第一个条件就有点厉害了。
考虑为了让 \(min \le x + k - 1\) 是不好做的，因为我们不知道最小值的位置。
那么我们考虑通过差分数组找到最小值的位置，然后固定一个数所有数就都固定了。
O(x^3 \log n)