Задачи с Timus

Revision ru1, by Felix_Mate, 2018-05-14 16:21:09

Хотелось бы узнать решение 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)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian Felix_Mate 2018-05-14 16:38:19 1105 (опубликовано)
ru1 Russian Felix_Mate 2018-05-14 16:21:09 712 Первая редакция (сохранено в черновиках)