Здравствуйте, Serge, Вы писали:

S>Есть такая задача: требуется найти количество строк длины n (n <= 100), которые не содержат в себе тандемных повторов длины от 1 до k (1 <= k <= 9) над заданным алфавитом из а букв (1 <= a <= 26). Тандемным повтором называется строка вида ww, где w — это некоторая последовательность букв (в этой последовательности от 1 до k букв).

S>Будут идеи?

Будем количество строк с повторами как функцию от n: R(n).
Всего строк длины n: U(n) = a**n.
Количество строк без повторов, соответственно: Q(n) = U(n)-R(n).

Сразу заметим, что мы получаем полиномы от переменной a, так что можем отложить все вычисления значений, а сперва находить векторы коэффициентов.

Итак. Пусть мы нашли все строки длины до n-1 включительно, и посчитали, сколько там чего.
Попробуем построить строки длины n с повторами.

R(n) = R(n-1) * a     -- дописали произвольную букву к каждой строке с повторами
     + Q(n-1)         -- взяли строку без повторов и удвоили ей хвост длины 1
     + Q(n-2)         -- взяли строку без повторов и удвоили ей хвост длины 2
     ...
     + Q(max(k,n-k))  -- взяли строку без повторов и удвоили ей хвост длины k (если она сама - длиной не меньше k)

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

Например, для хвоста длины 3:
xxxABC + ABC
xxxABCA + CA — откуда B=C, A=C, и на самом деле, xxxAAAA + AA. Понятно, что это строка с повтором, то есть, мы её не удваивали
xxxABCAB + B — откуда A=B, и это xxxAACAA, опять строка с повтором.

Для хвоста длины 4:
xxxABCD + ABCD
xxxABCDAB + AB => A=C, B=D, xxxABAB, строка с повтором
xxxABCDA + CDA, B=C=D=A, строка с повтором

Строго доказывать лень, но КАЖЕТСЯ, что мы действительно имеем дело с непересекающимися классами, поэтому можем суммировать как есть.

Теперь ещё уберём вторую функцию, чтоб получить чисто рекурсивное определение

R(n) = R(n-1) * a
     + a**(n-1) - R(n-1)
     + a**(n-2) - R(n-2)
     ...
     + a**(m)   - R(m), где m = max(k,n-k)

Начальные условия индукции: R(0) = 0 = [0] — далее я буду записывать полиномы векторами коэффициентов, старшими вперёд
Q(0) = [1].
Пустая строка ровно одна, и она, разумеется, без повторов.

R(1) = R(0)*a = [0]a = [0,0].
Q(1) = [1,0]
Единичные строки имеют вид A, и они, конечно, без повторов

R(2) = R(1)*a + Q(1)
= [0, 0, 0] +
  [0, 1, 0]
= [0, 1, 0]
Q(2) = [1,-1,0]

Строки длины 2 с повторами имеют вид AA — понятно, что их ровно a.

R(3) = R(2)*a + Q(2)
= [0, 1,  0, 0] +
  [0, 1, -1, 0]
= [0, 2, -1, 0]
Q(3) = [1,-2,1,0]

Строки длины 3 с повторами имеют вид AAx, ABB — их количество aa + a(a-1) = 2aa-a.

R(4) = R(3)*a + Q(3) + Q(2)
= [0, 2, -1,  0, 0] +
  [0, 1, -2,  1, 0] +
  [0, 0,  1, -1, 0]
= [0, 3, -2,  1, 0]
Q(4) = [1,-3,2,-1,0]

Строки длины 4 имеют вид AAxx, ABBx; ABCC (A≠B, B≠C, A?C), ABAB — их количество aaa + aa(a-1) + a(a-1)(a-1) + a(a-1) = 3aaa-2aa+a.

R(5) = R(4)*a + Q(4) + Q(3) =
[0, 3, -2,  1,  0, 0] +
[0, 1, -3,  2, -1, 0] +
[0, 0,  1, -2,  1, 0] =
[0, 4, -4,  1,  0, 0]
Q(5) = [1,-4,4,-1,0,0]

Строки длины 5 имеют вид AAxxx, ABBxx, ABCCx, ABABx; ABCDD, ABCBC (где C≠A, иначе бы это было удвоение хвоста у строки с повтором ABAB).

R(6) = R(5)*a + Q(5) + Q(4) + Q(3) =
= [0, 4, -4,  1,  0,  0, 0] +
  [0, 1, -4,  4, -1,  0, 0] +
  [0, 0,  1, -3,  2, -1, 0]
= [0, 5, -7,  2, -1, -1, 0]
Q(6) = [1,-5,7,-2,1,1,0]

Ну и так далее.
Заметим следующие вещи:
— коэффициент нулевой степени всегда равен 0, то есть, все ответы кратны a
— для вычисления рекуррентного выражения нам нужны последние k значений — R(n-k),...,R(n-1), то есть, мы можем хранить скользящее окно, а не кешировать всё подряд.

Ещё заметим: начиная с n=2k+1, мы перестаём ветвиться "хватит или не хватит длины в строках без повтора" (условие максимума) и выполняем одну и ту же операцию над нашими полиномами:

R(n) = R(n-1)*[1,0] + R(n-2)*[-1] + ... + R(n-k)*[-1] + [0,1,...,1]*[1]
R(n-1) = R(n-1)
R(n-2) = R(n-2)
....
R(n-k+1) = R(n-k)
[0,1,...,1] = [1,1,...,1]
[1] = [1]

То есть, умножаем вектор полиномов на матрицу M полиномов степени 1. Размер матрицы — (k+2)*(k+2).

                  / [1,0],  -1, -1, ..., -1, -1,     1,  0  \  полином R(n) текущий - считаем по формуле
                  |     1,   0,  0, ...,  0,  0,     0,  0  |  предшествующие - сдвигаем
                  |     0,   1,  0, ...,  0,  0,     0,  0  |
RR(n) = RR(n-1) * <    ...  ... ... ..., ... ...    ... ... >
                  |     0,   0,  0, ...,  1,  0,     0,  0  |  самый последний сдвинули
                  |     0,   0,  0, ...,  0,  0, [1,0],  1  |  полином единичек, нужен для нахождения дополнений
                  \     0,   0,  0, ...,  0,  0,     0,  1  /  константа единичка

Короче говоря,
RR(n) = RR(2k+1) * M**(n-2k-1)

Если целевое значение n очень большое, то мы можем возвести матрицу в соответствующую степень за логарифмическое от n время (но за квадратное от k, разумеется!).
Ну и там повылазят временные коэффициенты (n*k)**2, потому что у нас полиномы будут набухать. Но они и так повылазят, при линейном умножении вектора на матрицу.

Короче говоря, можем выгадать k*k*logn против k*n.
С достаточно хреновым коэффициентом при асимптоте — потому что мы станем жрать память, крутить хитрые циклы, ещё кешмиссы полезут...

Для n<=100 проще не париться, а выполнить линейный забег по формуле.