Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1243. Генератор текста
Модулярная арифметикаМатрицы
Динамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 26/09/2009 | Южно-Уральская открытая олимпиада, личное первенство (F) |
| 25/02/2013 | Занятие 18 (F) |
| 10/07/2023 | Лето 2023-7 сложные (F) |
| 07/03/2024 | ДП (повторение) (проводит BOGAT) (C) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Возьмем какой-нибудь осмысленный текст, предварительно удалив из него все знаки препинания, например, "alice was beginning to get very tired of sitting by her sister on the bank and of having nothing to do"
и подсчитаем частоту появления каждой буквы или пробела в этой фразе.
Мы можем сгенерировать текст, выбирая очередной символ с вероятностью, с которой этот символ
встречаются в исходной фразе, но результат будет слишком отличаться от естественного текста:
"iehehgv bwbertieitneisediiigiiidgrhs sn obi b i nlo nntthtesi oiin oihaetengdet ditfaoo hrhbebc".
Cлова невозможно произнести, они часто слишком длинные или совсем короткие. Намного лучший результат дает использование
алгоритма цепей Маркова, в котором анализируются вероятности появления пар символов
и очередной символ генерируется с учетом предыдущего символа текста:
"sinnk ve her walindof thinoto d tink aninged tind histo nof othe of bang tisingite oto to singing to".
Вероятность выбора очередного символа текста `A_i` прямо пропорцинальна вероятности появления пары `A_{i-1}A_i` в исходной фразе.
Для первого символа текста предыдущим (`A_0`) является пробел,
также пробелы добавляются в начале и в конце исходной фразы перед вычислением вероятности появления пар.
Длина слов в получившемся тексте более естественна,
их можно произнести, можно отметить появление английских слов bang и singing,
отсутствовавших в исходной фразе. Неспециалист даже может принять этот текст за текст на незнакомом ему языке.
Напишите программу, которая подсчитывает количество различных слов длины `N` в
бесконечном тексте, сгенерированном указанным алгоритмом.
Словом считается часть текста между пробелами, состоящая только из букв.
Первая строка ввода содержит два целых числа – длина слов `N` (`1\ ≤\ N\ ≤\ 10^9`) и число `P` (`10\ ≤\ P\ ≤\ 10^9`).
Вторая строка ввода содержит исходную фразу длиной не более 1000 символов, состоящую только из строчных латинских букв и символов пробела.
Вывести одно целое число – остаток от деления на число `P` количества различных слов длины `N` в
бесконечном сгенерированном тексте.
Пример ввода
2 100 alice was beginning to get very tired of sitting by her sister on the bank and of having nothing to do
Пример вывода
20
Пояснение в ходе соревнований:
Пусть пара символов `A_{i-1}B_j` встречается в исходной фразе `K_j` раз, где `B_j` кандидат на `i`-й символ генерируемого текста, тогда вероятность выбора символа `B_j` в качестве `A_i` равна `K_j/{sum_m\ K_m}`.
Т.е. если пара символов `"xy"` не встречается в исходной фразе, то она никогда не появится в генерируемом тексте.
