6960. Sum of distinct numbers

A positive integer n can be represented as a sum of distinct natural numbers in several ways. For example:

· for n = 5, there are 3 ways: 5, 2 + 3, 1 + 4;

· for n = 6, there are 4 ways: 6, 1 + 5, 1 + 2 + 3, 2 + 4.

Here, different permutations of the same set of summands are considered the same. For example, 1 + 2 + 3, 2 + 1 + 3 и 3 + 1 + 2 all count as the same way.

Input. The first line contains the number of test cases t (1 ≤ t ≤ 20).

Each of the following t lines contains a single integer n (1 ≤ n ≤ 2000).

Output. For each number n, print on a separate line the number of different ways to represent it as a sum of distinct positive integers, as described above.

Since the answer may be very large, print it modulo 100999.

Sample input	Sample output
4 5 6 10 200	3 4 10 50568

SOLUTION

dynamic programming

Algorithm analysis

Пусть dp[i][j] – количество способов представить число i в виде суммы различных чисел, каждое из которых не превышает j (0 ≤ i, j ≤ 2000).

Например:

· dp[6][0] = dp[6][1] = 0	· dp[6][4] = 2: 5 + 1, 4 + 2
· dp[6][2] = 0	· dp[6][5] = 3: 5 + 1, 4 + 2, 3 + 2 + 1
· dp[6][3] = 1: 3 + 2 + 1	· dp[6][6] = 4: 6, 5 + 1, 4 + 2, 3 + 2 + 1

Для суммы 0 существует ровно один способ – пустая сумма (ничего не складывать). Поэтому для всех j присвоим dp[0][j] = 1.

Значение dp[i][j] пересчитываем следующим образом:

· Если j > i, значит текущее максимальное число j больше, чем сумма i, и мы не можем его использовать. Тогда количество способов равно количеству способов представить i при помощи чисел от 1 до j – 1:

dp[i][j] = dp[i][j – 1]

· Если j ≤ i, то мы можем либо не использовать число j (тогда способов dp[i][j – 1]), либо использовать j (тогда мы ищем количество способов представить сумму i – j при помощи чисел от 1 до j – 1, чтобы избежать повторного использования числа j):

dp[i][j] = dp[i][j – 1] + dp[i – j][j – 1]

Для заданного числа n ответом будет значение dp[n][n].

Algorithm implementation

Declare the constants.

#define MAX 2001

#define MOD 100999

Объявим массив dp.

vector<vector<int>> dp(MAX, vector<int>(MAX, 0));

Базовый случай. Единственный способ получить сумму 0 – это пустое множество.

for (j = 0; j < MAX; j++)

dp[0][j] = 1;

Вычисляем значения массива dp.

for (i = 1; i < MAX; i++)

for (j = 1; j < MAX; j++)

{

if (j > i)

dp[i][j] = dp[i][j - 1];

else

dp[i][j] = (dp[i][j - 1] + dp[i - j][j - 1]) % MOD;

}

Читаем количество тестов tests.

scanf("%d", &tests);

Последовательно обрабатываем tests тестов. Для каждого входного значения n выводим ответ dp[n][n].

while (tests--)

{

scanf("%d", &n);

printf("%d\n", dp[n][n]);

}