365. 整数划分
时间限制：1000 MS 内存限制：64 MB
题目描述
# 整数划分 ## 题目描述 一个正整数 $n$ 可以表示成若干个正整数之和： $$ n=n_1+n_2+\cdots+n_k, $$ 其中 $n_1\ge n_2\ge\cdots\ge n_k\ge 1$，且 $k\ge 1$。我们将这样的一种表示称为正整数 $n$ 的一种划分。 划分中允许同一个正整数重复出现，仅排列顺序不同的表示视为同一种划分。 现在给定一个正整数 $n$，请你求出 $n$ 共有多少种不同的划分，并输出划分数量对 $10^9+7$ 取模的结果。 ## 输入格式 从文件 `partition.in` 中读入数据。 共一行，包含一个整数 $n$。 ## 输出格式 将结果输出到文件 `partition.out`。 共一行，包含一个整数，表示 $n$ 的划分数量对 $10^9+7$ 取模的结果。 ## 数据范围 $1\le n\le 1000$。 ## 样例输入 ``` 5 ``` ## 样例输出 ``` 7 ``` ## 样例解释 正整数 $5$ 共有以下 $7$ 种不同的划分： - $5=5$； - $5=4+1$； - $5=3+2$； - $5=3+1+1$； - $5=2+2+1$； - $5=2+1+1+1$； - $5=1+1+1+1+1$。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 空间限制：$64$ MB。