Хотелось бы узнать решение 2х задач с тимуса
1)http://acm.timus.ru/problem.aspx?space=1&num=1677 Знаю, как её решать неоптимально (проблемы с ML, но не с TL). Можно получить точную дробь-ответ в длинной арифметике. У нас цепь маркова, переходы задаются с помощью граней префикса строки, состояния- префиксы длины 0,1,2,...n=len(s). Переход из состояния i в состояние j происходит с P=1/A (A-мощность алфавита), i<n и с P=1 из n в n. Можно написать соответствующие матожидания и получить СЛАУ. Решать СЛАУ можно за O(n), введя коэффициенты a[i],b[i] и с начального значения их пересчитывать. Проблема возникает с тем, что они быстро растут и потому ML. Код: https://ideone.com/41LFtk
2)