Число различных подпоследовательностей

1. Идея

Нужно посчитать количество различных непустых подпоследовательностей строки.

Если бы все символы были разными, всё было бы просто: каждая уже найденная подпоследовательность может либо взять новый символ, либо не взять его, значит количество удваивается.

Но в строке могут повторяться буквы. Тогда при добавлении очередного символа часть новых подпоследовательностей окажется не новыми, а уже встречавшимися раньше. Значит, нужно уметь вычитать дубликаты.

Для этого используется динамика по префиксу строки и массив last, который хранит вклад последнего появления каждой буквы.

2. Наблюдения

Обозначим через dp количество различных подпоследовательностей текущего префикса, включая пустую подпоследовательность.

Изначально:

• для пустой строки есть ровно одна подпоследовательность — пустая,
• значит dp = 1.

Теперь рассмотрим очередной символ c.

Что будет без учёта повторов

Каждую уже существующую подпоследовательность можно:

• оставить как есть;
• дописать в конец символ c.

Значит, формально получилось бы 2 * dp.

Откуда берутся дубликаты

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

Сколько именно таких повторов?

Пусть предыдущее появление буквы c было обработано раньше. В тот момент число различных подпоследовательностей было равно некоторому значению. Все подпоследовательности, полученные тогда дописыванием c, сейчас будут продублированы.

Именно это значение и хранится в last[c].

Тогда переход такой:

• берём 2 * dp,
• вычитаем last[c].

Получаем:

• new_dp = 2 * dp - last[c].

После этого нужно обновить last[c], чтобы при следующем появлении этой буквы знать нужное старое значение. Туда записывается текущее старое dp, то есть количество подпоследовательностей до обработки нового символа.

3. Алгоритм

1. Считать строку s.
2. Создать массив last из 26 элементов, заполненный нулями.
   • last[i] — значение dp перед последним появлением буквы с номером i.
3. Завести dp = 1.
   • Это число различных подпоследовательностей текущего префикса, включая пустую.
4. Для каждого символа c строки:
   • найти его индекс x = c - 'a';
   • сохранить old_dp = dp;
   • пересчитать dp = (2 * dp - last[x]) mod MOD;
   • присвоить last[x] = old_dp.
5. В конце вычесть пустую подпоследовательность:
   • ответ dp - 1.
6. Вывести ответ по модулю 1000000007.

4. Почему это работает

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

Пусть уже обработан некоторый префикс строки, и dp — число всех различных подпоследовательностей этого префикса, включая пустую.

Рассмотрим следующий символ c.

Все возможные подпоследовательности после добавления c

Любая подпоследовательность нового префикса бывает двух типов:

1. Не использует новый символ c.

   • Таких dp, это все старые подпоследовательности.

2. Использует новый символ c как последний выбранный символ.

   • Их тоже можно получить из каждой старой подпоследовательности, просто дописав c.
   • Формально снова dp штук.

Итого было бы 2 * dp.

Какие из них посчитались дважды

Если буква c раньше не встречалась, дубликатов нет.

Если буква c уже встречалась, то некоторые строки уже были получены при предыдущем появлении c.

Какие именно?

При предыдущем появлении c мы брали все подпоследовательности, существовавшие до него, и дописывали к ним c. Все такие строки уже были добавлены тогда. Их количество равно числу различных подпоследовательностей, существовавших до того появления c.

Именно это число хранится в last[c].

Значит, число действительно новых подпоследовательностей равно:

• 2 * dp - last[c].

После обработки текущего символа значение last[c] нужно обновить: теперь последним появлением c становится текущая позиция, а число подпоследовательностей до неё равно old_dp.

Таким образом, формула перехода корректна на каждом шаге, а в конце dp хранит число всех различных подпоследовательностей всей строки, включая пустую. Поэтому ответ равен dp - 1.

5. Сложность

Пусть длина строки равна n.

• Время: O(n), потому что каждый символ обрабатывается один раз.
• Память: O(1), потому что используется только массив last из 26 элементов.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    const long long MOD = 1000000007LL;

    string s;
    cin >> s;

    vector<long long> last(26, 0);
    long long dp = 1; // количество различных подпоследовательностей, включая пустую

    for (char c : s) {
        int x = c - 'a';
        long long old_dp = dp;
        dp = (2 * dp % MOD - last[x] + MOD) % MOD;
        last[x] = old_dp;
    }

    long long answer = (dp - 1 + MOD) % MOD;
    cout << answer << "\n";
    return 0;
}

7. Код на Python 3

MOD = 1000000007

s = input().strip()

last = [0] * 26
dp = 1  # включая пустую подпоследовательность

for c in s:
    x = ord(c) - ord('a')
    old_dp = dp
    dp = (2 * dp - last[x]) % MOD
    last[x] = old_dp

print((dp - 1) % MOD)