|
|
back to boardWA 5 Мне кажется, что моя формула верна. Пусть 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 Я неправильно записал формулу-рассуждения верные. Ошибка в 3 выводе. Нужно так: => f(n)=n*(2*n-1)*f(n-1)+n*(n-1)*f(n-2). |
|
|