Readme

3098.Find-the-Sum-of-Subsequence-Powers

表面上求的是“子序列”，其实求的是“子集”，对于顺序没有要求。所以我们会将nums先排序。此时任何“子序列”里的最小元素之差，必然出现在所按顺序选取的两个元素之间。

考虑到n=50不大，可以枚举出所有的元素之差，比如元素a和元素b，约定它们是子序列里的“最小元素之差”（记做d），求这样的长度为k的子序列有多少个。这可以判断出至少有n^3的解法。而事实上，很意外地，本题可以容忍n^5的复杂度。所以这个思路是可行的。

接下来我们就解决上面提出的问题：在一个有序数组nums里，对于元素a和元素b，约定它们是子序列里的“最小元素之差”（记做d），求这样的长度为K的子序列有多少个。事实上，我们可以用DP求出在[1,a]区间内有多少相邻元素之差大于d的子序列。我们令dp1[i][j]表示以i结尾的、长度为j、且相邻元素跨度大于d的子序列个数。我们只需要找到前一个符合条件的位置k，满足nums[i]-nums[k]>d，就有dp1[i][j] += dp1[k][j-1]，将所有符合条件的j遍历一遍，就可以求出dp[i][j].

同理，我们从后往前进行DP，求出在[b,n]区间里有多少相邻元素之差大于d的子序列。可以求解dp2[i][j]表示以i开头的、长度为j、且相邻元素跨度大于等于d的子序列个数。

这样，我们只需要将期望长度K分配给[a,b]的前后两段，假设分别是t和K-t，就可以得到组合数dp[a][t]*dp[b][K-t]，对应的就是包含a和b的、符合条件的子序列的个数。我们对于所有t=1,2,...K-1，将组合数求和即可。

特别注意，dp1和dp2的定义略有不同，前者要求跨度大于d，后者要求跨度大于等于d。这是因为一个子序列里可能有多个最小跨度d，我们约定只认为第一个出现的最小跨度d是我们的枚举对象。所以在[1,a]区间内，我们不接受相邻元素跨度恰好为d的情况。