思路
不难想到一个记录前缀最大值的 \(\text{dp}\), 但是不难发现所有值域相关算法全部倒闭了
离散化之后变成每次可以选一个值域区间, 然后值域 \(\to \,n\)
令 \(f_{i, j}\) 表示处理到第 \(i\) 个位置, 且当前前缀最大值已经到达值域区间 \(j\) 的方案数
显然可以分段刻画
\[f_{i, j} \gets
\sum_{k = 1}^{j - 1} f_{k, j - 1} \Bigg(\sum_{c = 0}^{i - k - 1} {i - k - 1 \choose c} {siz \choose i - k - c}\Bigg)
\]
不难发现
\[\sum_{c = 0}^{i - k - 1} {i - k - 1 \choose c} {siz \choose i - k - c} = {siz + i − k − 1 \choose i − k}
\]
递推组合数即可 \(\mathcal O(n^3)\) 转移完
总结
范德蒙德卷积:
\[\sum_{i = 0}^r {n \choose i} {m \choose r - i} = {n + m \choose r}
\]
离散化还是太帅了