上升序列的数量

关于上升序列的数量以及状态压缩的一点思考

---

题意

给一个长度为 $n$ 的序列，每个数为 $[1,m]$ 中的任意一个数，问满足整个序列都不递减的序列数量。($n,m$ 都很小)

分析

公式

$$C(n+m-1.m-1)$$
$pp$ 太巨了啊，$fans$。

解法1

枚举整个序列用了几个数，用组合数可以 $n^2$ 求解。

解法2

$dp$ 用一个前缀和优化也是可以 $n^2$ 的。

状态压缩

$$ sum_i = sum_j*n + a[j]$$