Балансировка камней.

Вам даны рычажные весы. На левой чаше весов лежит один камень с весом W<2N. У вас есть свое множество камней: 1, 2, 4, … , 2N-1. 
Определите сколькими способами можно расположить некоторые из этих камней на чашах весов так, чтобы уравновесить их. Выведите это значение по модулю D.
Входные данные (input.txt):
В первой строке записаны три числа: N, L, D. (1<=L<=N<=1000000, 1<=D<=100).
Далее во второй строке ровно L символов – двоичная запись числа W.
Выходные данные (output.txt):
Единственное число – количество способов, взятое по модулю D.

Примеры:
Input.txt
6 4 6 
1000
Output.txt
3

Input.txt
6 6 100 
100110
Output.txt
5

Ссылка:
acm-test.bsu.by -> Задания -> Теория алгоритмов -> Рекуррентные
, только вы не сможете зайти без регистрации.

См. исходник, прикреплённый к сообщению. Как можно ускорить процесс? В системе acm-test проходит один тест из 14, на остальные пишет либо ошибка времени выполнения, либо нарушен предел времени.

Добавлено через 2 минуты и 47 секунд
Вот исходник.

Добавлено через 6 минут и 11 секунд
Имеется в виду 2 в степени N, а не 2*N. Всё степени, не умножение.

Присоединённый файл ( Кол-во скачиваний: 26 )
 Stones.cpp 2,14 Kb

Не читал вашего решения, но вроде можно решить простой линейной динамикой D[L][2], которую можно назвать и рекуррентной формулой.

Это сообщение отредактировал(а) maxdiver - 9.3.2009, 00:35

Только как там субмитить? Что, просто так зарегаться и открыть нельзя?

В общем, там на acm-test система "логин - номер зачётки; пароль", она по номеру смотрит, какая группа, и открывает только текущее задание. Без номера, соответственно, ничего не откроется, это я просёк уже после того, как дал ссылку.
Спасибо за совет, я не волшебник, я только учусь ))) Попробую, скажу, что получится!

Что ж, тогда я своё решение не проверю никак. На ручных тестах работает, с идеей вроде всё в порядке, но здесь я, конечно, выкладывать решение не буду.

В длинной арифметике в моём решении вообще нет нужды, так что вы, скорее всего, зашли не в ту сторону. Лучше попытаться понять, как и почему ответ изменяется, когда к числу слева дописывается единичка или нолик, отсюда и получаются довольно простые формулы.

Супер! Сейчас скинул решение, 13 из 14 тестов прошли! В 14ом нарушен предел времени, надо чуть-чуть посмотреть, где и почему это могло произойти. Вы правы, меня понесло совсем не туда, в рекурсию, а не в динамическое программирование. 

Помнится, задачу решал, людей через мост надо было переводить, каждый со своей скоростью, одновременно через мост могут идти только двое, дело происходит ночью, а фонарик один. Так там было что-то около ста тысяч человек, естественно, что рекурсия шла лесом. А потом нашёл рекуррентное соотношение, и всё стало очень быстро происходить! А тут сходу тормознул. Правда, писать начал только вчера. С такими темпами сегодня хочется закончить.

Ещё раз спасибо!