\(m = \sqrt{n}+1\)
对于大于 \(m\) 的数,采用另外一种方式
\(x > m\) --> 其数量 \(< m\)
记 \(g[i][j]\) 表示用了 \(i\) 个大于等于 \(m\) 的数 和为 \(j\) 的方案数
初始状态 : \(g[0][0] = 1\);
转移方程 : \(g[i][j] = g[i-1][j-m] + g[i][j-i];\)
在序列中加一个 m 把当前序列中的的每个数 +1
时间复杂度:$O(n\sqrt{n}) $
Last but not least : 把两部分结合一下
枚举第一个部分的总和为 \(j\)，那第二个部分的总和为 \(n-j\),
把两者的方案数乘起来记入答案中:
$\sum_{j=0}^{n}(f[m-1][j]\times \sum_{i=0}^{m}g[i][n-j] ) $