#B. 整数划分

    传统题 文件IO:divide 1000ms 256MiB

整数划分

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

将正整数 nn 表示成一系列正整数之和: n=n1+n2++nkn=n_1+n_2+⋯+n_k

其中 n1n2nk1n_1≥n_2≥⋯≥n_k≥1k1k≥1

正整数 nn 的这种表示称为正整数 nn 的划分。求正整数 nn 的不同划分个数。

例如正整数 66 有如下 1111 种不同的划分:

65+14+24+1+13+33+2+13+1+1+12+2+22+2+1+12+1+1+1+11+1+1+1+1+16、5+1、4+2,4+1+1、3+3,3+2+1,3+1+1+1、2+2+2,2+2+1+1,2+1+1+1+1、1+1+1+1+1+1

输入格式

第一行是测试数据的数目 M(1M10)M(1≤M≤10) 。以下每行均包含一个整数 n(1n1000)n(1≤n≤1000)

输出格式

输出每组测试数据有多少种分法,最终结果模 109+910^9+9

格式说明输出时每行末尾的多余空格,不影响答案正确性

输入、输出要求要求使用「文件输入、输出」的方式解题,输入文件为 divide.in,输出文件为 divide.out

样例输入

1
6

样例输出

11

七年级少年班9.24作业

未认领
状态
已结束
题目
5
开始时间
2023-9-24 0:00
截止时间
2023-10-10 23:59
可延期
24 小时