在我的个人博客中阅读

50 分：

暴力枚举即可

100 分：

设输入的序列为 $a_i$。容易发现，如果我们按原序列从左往右扫，扫到第 $i$ 个位置时，我们要考虑的是这一个位置要填什么以及 $a_i$ 要填到哪个位置上。

并且一共只有 5 种情况：

• $a_i$ 填到 $i$ 上；
• 拿一个比 $a_i$ 小的数填到 $i$ 上并且 $a_i$ 填到比 $i$ 小的位置上；
• 拿一个比 $a_i$ 小的数填到 $i$ 上并且 $a_i$ 填到比 $i$ 大的位置上；
• 拿一个比 $a_i$ 大的数填到 $i$ 上并且 $a_i$ 填到比 $i$ 大的位置上；
• 拿一个比 $a_i$ 大的数填到 $i$ 上并且 $a_i$ 填到比 $i$ 小的位置上

那么我们记 $f_{i,j,p}$ 表示现在填完第 $i$ 个数，比 $i$ 小（包括 $i$）的有 $j$ 个没填，并且算出来的价值为 $p$ 的方案数。假设我们现在考虑 $i+1$ 位填的数，分别考虑以上的五种情况。不过这里要注意的一点就是当这个位置填的数比它小时，是无法确定究竟是 $j$ 个当中的哪一个，因此这一部分的价值需要在之前填上 $j$ 这一位的时候就统计在答案中。

为了方便表述，借助标程的代码段进行解释（一些边界判断和取模略去）：

f[i+1][j][p+a[i+1]] += f[i][j][p];//第 i+1 位填 a[i+1]，不会产生新的未填项，并且产生新贡献为 a[i+1]
f[i+1][j-1][p] += f[i][j][p]*j*j;//第 i+1 位填比 a[i+1] 小的数并且 a[i+1] 填到比 i+1 小的位置上。减少一个未填项，产生新贡献为 0（这些贡献之前之前已经计算）
f[i+1][j][p+a[i+1]] += f[i][j][p]*j;//第 i+1 位填比 a[i+1] 小的数并且 a[i+1] 填到比 i+1 大的位置上。未填项数目不改变，产生新贡献为 a[i+1]（贡献来自 a[i+1] 填到的那位）
f[i+1][j+1][p+2*a[i+1]] += f[i][j][p];//第 i+1 位填比 a[i+1] 大的数并且 a[i+1] 填到比 i+1 大的位置上。未填项数目 +1，产生新贡献为 2*a[i+1]（贡献来自 i+1 位和 a[i+1] 填到的那位）
f[i+1][j][p+a[i+1]] += f[i][j][p]*j;//第 i+1 位填比 a[i+1] 大的数并且 a[i+1] 填到比 i+1 小的位置上。未填项数目不改变，产生新贡献为 a[i+1]（贡献来自 i+1 位）