основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
ChemicalBurn
новичок


Рег.: 08/14/06
Сообщений: 5
Из: Санкт-Петербург
1459 с Тимуса
      #11850 - 08/14/06 07:27 AM

Напоминает динамику по профилю, вот только не знаю так это или нет?

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: 1459 с Тимуса [Re: ChemicalBurn]
      #11851 - 08/14/06 11:48 AM

При M=10^9 вряд-ли...

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
EfremovAleksei
здесь был не раз


Рег.: 03/05/06
Сообщений: 36
Re: 1459 с Тимуса [Re: _МГ_]
      #11852 - 08/14/06 09:52 PM

Быстрое возведение матрицы в степень

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
ChemicalBurn
новичок


Рег.: 08/14/06
Сообщений: 5
Из: Санкт-Петербург
Re: 1459 с Тимуса [Re: EfremovAleksei]
      #11861 - 08/15/06 09:57 AM

А можно поподробнее?

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
_МГ_
новичок
*****

Рег.: 08/14/06
Сообщений: 16
Из: Санкт-Петербург
Re: 1459 с Тимуса [Re: EfremovAleksei]
      #11862 - 08/15/06 02:03 PM

И какие там матрицы?

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
EfremovAleksei
здесь был не раз


Рег.: 03/05/06
Сообщений: 36
Re: 1459 с Тимуса [Re: _МГ_]
      #11863 - 08/15/06 09:26 PM

Конкретно эту задачу, я не пытался сдавать.
Но суть примерно в следующем:
Кол-во путей лучника - кол-во способов расположить на поле
замкнутую трубу(чтобы она проходила по каждой клетке 1 раз)*2.
Профиль - разрез труб с указанием, какая труба в какую приходит.
Изначально A[i,j]=1 - можно ли перейти от профиля i к профилю j.
Понятно(из алгоритма умножения матриц), что A^M [i,j] - это кол-во способов перейти от профиля i к j,перейдя по M-1 промежуточному профилю.

Похожая задача - 'Cимпатичные узоры-2' с Зимних сборов-2003


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 385 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 12510

Rate this topic

Переход в