ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1747. Осмотр владений

WA 5
Послано Felix_Mate 29 май 2017 13:00
Мне кажется, что моя формула верна.
Пусть f(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём любые два соседние числа различны; g(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём существует только одна пара соседних равных чисел.
Тогда f(n)=n*(2*n-2)*f(n-1)+n*g(n-1), g(n)=n*(2*n-1)*f(n-1)+n*g(n-1) => f(n)=g(n)-n*f(n-1) => g(n-1)=f(n-1)+(n-1)*f(n-2) => f(n)=n*((2*n-1)*f(n-1)+n*(n-1)*f(n-2)).
f(1)=0, f(2)=2 (mod p).
Ответ на задачу f(n-1) mod p.

Хотелось бы увидеть ответы на следующие тесты:
5 10000000
6 10000000
7 10000000

Edited by author 29.05.2017 13:01
Re: WA 5
Послано Felix_Mate 30 май 2017 19:51
Я неправильно записал формулу-рассуждения верные. Ошибка в 3 выводе. Нужно так: => f(n)=n*(2*n-1)*f(n-1)+n*(n-1)*f(n-2).