Сообщение Re: Разборчивые строки от 09.07.2018 14:32
Изменено 09.07.2018 14:35 Кодт
Re: Разборчивые строки
Здравствуйте, 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 с повторами.
Тут нужно убедиться, что удвоение более длинного хвоста не эквивалентно удвоению более короткого хвоста более длинной строки без повторов. То есть, что классы не пересекаются, и мы не посчитали одну строку дважды.
Например, для хвоста длины 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(0) = 0 = [0] — далее я буду записывать полиномы векторами коэффициентов, старшими вперёд
Q(0) = [1].
Пустая строка ровно одна, и она, разумеется, без повторов.
R(1) = R(0)*a = [0]a = [0,0].
Q(1) = [1,0]
Единичные строки имеют вид A, и они, конечно, без повторов
Строки длины 2 с повторами имеют вид AA — понятно, что их ровно a.
Строки длины 3 с повторами имеют вид AAx, ABB — их количество aa + a(a-1) = 2aa-a.
Строки длины 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.
Строки длины 5 имеют вид AAxxx, ABBxx, ABCCx, ABABx; ABCDD, ABCBC (где C≠A, иначе бы это было удвоение хвоста у строки с повтором ABAB).
Ну и так далее.
Заметим следующие вещи:
— коэффициент нулевой степени всегда равен 0, то есть, все ответы кратны a
— для вычисления рекуррентного выражения нам нужны последние k значений — R(n-k),...,R(n-1), то есть, мы можем хранить скользящее окно, а не кешировать всё подряд.
Ещё заметим: начиная с n=2k+1, мы перестаём ветвиться "хватит или не хватит длины в строках без повтора" (условие максимума) и выполняем одну и ту же операцию над нашими полиномами:
То есть, умножаем вектор полиномов на матрицу M полиномов степени 1. Размер матрицы — (k+2)*(k+2).
Короче говоря,
RR(n) = RR(2k+1) * M**(n-2k-1)
Если целевое значение n очень большое, то мы можем возвести матрицу в соответствующую степень за логарифмическое от n время (но за квадратное от k, разумеется!).
Ну и там повылазят временные коэффициенты (n*k)**2, потому что у нас полиномы будут набухать. Но они и так повылазят, при линейном умножении вектора на матрицу.
Короче говоря, можем выгадать k*k*logn против k*n.
С достаточно хреновым коэффициентом при асимптоте — потому что мы станем жрать память, крутить хитрые циклы, ещё кешмиссы полезут...
Для n<=100 проще не париться, а выполнить линейный забег по формуле.
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,1], 0 | полином единичек, нужен для нахождения дополнений
\ 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 проще не париться, а выполнить линейный забег по формуле.
Re: Разборчивые строки
Здравствуйте, 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 с повторами.
Тут нужно убедиться, что удвоение более длинного хвоста не эквивалентно удвоению более короткого хвоста более длинной строки без повторов. То есть, что классы не пересекаются, и мы не посчитали одну строку дважды.
Например, для хвоста длины 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(0) = 0 = [0] — далее я буду записывать полиномы векторами коэффициентов, старшими вперёд
Q(0) = [1].
Пустая строка ровно одна, и она, разумеется, без повторов.
R(1) = R(0)*a = [0]a = [0,0].
Q(1) = [1,0]
Единичные строки имеют вид A, и они, конечно, без повторов
Строки длины 2 с повторами имеют вид AA — понятно, что их ровно a.
Строки длины 3 с повторами имеют вид AAx, ABB — их количество aa + a(a-1) = 2aa-a.
Строки длины 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.
Строки длины 5 имеют вид AAxxx, ABBxx, ABCCx, ABABx; ABCDD, ABCBC (где C≠A, иначе бы это было удвоение хвоста у строки с повтором ABAB).
Ну и так далее.
Заметим следующие вещи:
— коэффициент нулевой степени всегда равен 0, то есть, все ответы кратны a
— для вычисления рекуррентного выражения нам нужны последние k значений — R(n-k),...,R(n-1), то есть, мы можем хранить скользящее окно, а не кешировать всё подряд.
Ещё заметим: начиная с n=2k+1, мы перестаём ветвиться "хватит или не хватит длины в строках без повтора" (условие максимума) и выполняем одну и ту же операцию над нашими полиномами:
То есть, умножаем вектор полиномов на матрицу M полиномов степени 1. Размер матрицы — (k+2)*(k+2).
Короче говоря,
RR(n) = RR(2k+1) * M**(n-2k-1)
Если целевое значение n очень большое, то мы можем возвести матрицу в соответствующую степень за логарифмическое от n время (но за квадратное от k, разумеется!).
Ну и там повылазят временные коэффициенты (n*k)**2, потому что у нас полиномы будут набухать. Но они и так повылазят, при линейном умножении вектора на матрицу.
Короче говоря, можем выгадать k*k*logn против k*n.
С достаточно хреновым коэффициентом при асимптоте — потому что мы станем жрать память, крутить хитрые циклы, ещё кешмиссы полезут...
Для n<=100 проще не париться, а выполнить линейный забег по формуле.
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 проще не париться, а выполнить линейный забег по формуле.