题目描述

给定两个整数 $n$ 和 $m$，询问满足如下条件的序列 $a$ 的数量：

• 序列 $a$ 的长度为 $n$ ；
• 序列 $a$ 的值均大于等于 0 且小于等于 $m$，形式化地说，$0 \leq a_i \leq m \ (1 \leq i \leq m)$；
• $a_1 \leq a_2 \leq a_3 \leq \cdots \leq a_n$，表示序列 $a$ 是一个非递减序列；

题解

前缀和优化DP

对于这种计数类问题，而且还需要取模的情况下，往 DP 方面想准没错了。

朴素DP