[agc041_d]Problem Scores

ID: 1955

传统题

2000ms

1024MiB

难度: 8

上传者:

标签>

3000+

有 $n$ 道还未赋分的题目，你需要给这 $n$ 道题目赋分。
设第 $i$ $i$ 道题目的分数为 $A_i$ $A_{i}$ 。给题目赋分的方案需要满足：
- 对于任意 $i \in [2, n]$ ， $A_{i-1} \leq A_{i}$ 。
- 对于任意 $i \in [1, n]$ ， $1 \leq A_{i} \leq n$ 。
- 对于任意一个大小为 $k$ （ $1 \leq k < n$ ）的题目子集 $S$ 和任意一个大小为 $k+1$ 的题目子集 $T$ ，需要满足： $\sum_{x \in S}A_x < \sum_{x\in T}A_x$ 。
你需要计算，有多少种给题目赋分的方案，使得能满足上述三个条件。请求出答案对 $M$ 取模的结果。

#agc041d. [agc041_d]Problem Scores