Разбор задачи «Кратные последовательности»

Идея задачи

Нужно посчитать количество последовательностей длины k, состоящих из чисел от 1 до n, таких что каждый следующий элемент кратен предыдущему.

То есть для последовательности

a[1], a[2], ..., a[k]

должно выполняться:

a[i] | a[i + 1] для всех 1 <= i < k.

Требуется вывести количество таких последовательностей по модулю 10^9 + 7.

Почему перебор не подходит

Если пытаться перебрать все последовательности целиком, то вариантов будет n^k, что слишком много уже при небольших значениях n и k.

Например, даже при n = 10 и k = 10 это уже 10^10 последовательностей.

Поэтому нужно искать способ считать ответ не по самим последовательностям, а по их свойствам.

Наблюдение

Важно не то, как именно мы пришли к текущему числу, а только то, каким числом заканчивается последовательность.

Это подсказывает динамическое программирование.

Обозначим:

• dp[len][x] — количество корректных последовательностей длины len, оканчивающихся числом x.

Тогда:

• для длины 1 любая последовательность из одного числа корректна;
• значит, dp[1][x] = 1 для всех x от 1 до n.

Теперь поймем переход.

Если последовательность длины len - 1 заканчивается числом x, то следующим числом может быть любой кратный x:

x, 2x, 3x, ...

пока значение не превысит n.

Значит, из состояния x мы добавляем вклад во все числа m, где m % x == 0.

Формула перехода

Если мы уже знаем значения для длины len - 1, то для длины len делаем так:

for x from 1 to n:
    for m from x to n step x:
        dp[len][m] += dp[len - 1][x]

Иными словами, если предыдущий элемент равен x, то следующий может быть любым кратным x.

Почему это корректно

Докажем корректность динамики.

Рассмотрим все корректные последовательности длины len, которые заканчиваются числом m.

У такой последовательности предпоследний элемент обязан делить m. Обозначим его через x. Тогда первые len - 1 элементов образуют корректную последовательность длины len - 1, оканчивающуюся в x.

Значит, каждая последовательность длины len, оканчивающаяся в m, получается из некоторой последовательности длины len - 1, оканчивающейся в делителе x числа m.

С другой стороны, любую корректную последовательность длины len - 1, оканчивающуюся в x, можно продолжить числом m, если m кратно x.

Именно это и делает наш переход. Мы перебираем все возможные x и добавляем их вклад во все допустимые m.

Следовательно, динамика учитывает все и только корректные последовательности, без пропусков и повторов.

Оптимизация памяти

Хранить всю таблицу dp[len][x] не обязательно.

Чтобы посчитать слой длины len, нужен только предыдущий слой длины len - 1.

Поэтому можно хранить:

• dp[x] — текущий слой;
• ndp[x] — следующий слой.

После вычисления очередного слоя просто меняем массивы местами.

Это уменьшает расход памяти с O(nk) до O(n).

Оценка сложности

Для каждого значения длины мы перебираем все числа x от 1 до n и все их кратные.

Число операций на одном слое равно:

n/1 + n/2 + n/3 + ... + n/n

Это оценивается как O(n log n).

Итоговая сложность:

• по времени: O(k * n * log n)
• по памяти: O(n)

При n, k <= 2000 это уверенно проходит.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> dp(n + 1, 1), ndp(n + 1, 0);

    for (int len = 2; len <= k; ++len) {
        fill(ndp.begin(), ndp.end(), 0);

        for (int x = 1; x <= n; ++x) {
            for (int m = x; m <= n; m += x) {
                ndp[m] += dp[x];
                if (ndp[m] >= MOD) {
                    ndp[m] -= MOD;
                }
            }
        }

        dp.swap(ndp);
    }

    int ans = 0;
    for (int x = 1; x <= n; ++x) {
        ans += dp[x];
        if (ans >= MOD) {
            ans -= MOD;
        }
    }

    cout << ans << '\n';
    return 0;
}

Реализация на Python

MOD = 10**9 + 7

n, k = map(int, input().split())

dp = [1] * (n + 1)

for _ in range(2, k + 1):
    ndp = [0] * (n + 1)
    for x in range(1, n + 1):
        val = dp[x]
        for m in range(x, n + 1, x):
            ndp[m] += val
            if ndp[m] >= MOD:
                ndp[m] -= MOD
    dp = ndp

print(sum(dp[1:]) % MOD)

Разбор на маленьком примере

Пусть n = 3, k = 2.

Тогда для длины 1:

• последовательностей, оканчивающихся в 1: 1
• в 2: 1
• в 3: 1

То есть:

dp = [1, 1, 1], если смотреть только на значения для 1..3.

Теперь строим длину 2.

Из 1 можно перейти в 1, 2, 3. Из 2 можно перейти только в 2. Из 3 можно перейти только в 3.

Получаем:

• в 1: 1
• в 2: 2
• в 3: 2

Сумма равна 5.

Это и есть ответ:

[1, 1]
[1, 2]
[1, 3]
[2, 2]
[3, 3]

Типичные ошибки

1. Неправильное понимание условия

Иногда путают условия:

• «следующий делит предыдущий»
• и «следующий кратен предыдущему»

Здесь нужно именно:

a[i + 1] % a[i] == 0

2. Попытка хранить всю таблицу без необходимости

Полная таблица тоже пройдет, но она не нужна. Двух массивов достаточно.

3. Ошибка в переходе

Правильный цикл по кратным выглядит так:

for (int m = x; m <= n; m += x)

А не наоборот.

4. Забыли модуль

Количество последовательностей быстро растет, поэтому все вычисления нужно вести по модулю 10^9 + 7.

Вывод

В этой задаче ключевая идея состоит в том, чтобы перейти от перебора всех последовательностей к подсчету количества способов закончить последовательность каждым числом.

Состояние динамики определяется только:

• длиной последовательности,
• ее последним элементом.

А переход строится по кратным.

Это дает достаточно быстрое и аккуратное решение, которое хорошо укладывается в ограничения.