Условие:
Напиши на c++ используя дискретное преобразование Фурье: Двое дуэлянтов решили выбрать в качестве места проведения поединка тёмную аллею. Вдоль этой аллеи растёт n деревьев и кустов. Расстояние между соседними объектами равно одному метру. Дуэль решили проводить по следующим правилам. Некоторое дерево выбирается в качестве стартовой точки. Затем два дерева, находящихся на одинаковом расстоянии от исходного, отмечаются как места для стрельбы. Дуэлянты начинают движение от стартовой точки в противоположных направлениях. Когда соперники достигают отмеченных деревьев, они разворачиваются и начинают стрелять друг в друга.
Дана схема расположения деревьев вдоль аллеи. Требуется определить количество способов выбрать стартовую точку и места для стрельбы согласно правилам дуэли.
Формат входных данных
Задана одна строка, состоящая из символов «0» и «1» - схема аллеи. Деревья обозначаются символом «1», а кусты - символом «0». Длина строки не превосходит 100000 символов.
Формат выходных данных
Выведите количество способов выбрать стартовую точку и места для
стрельбы согласно правилам дуэли.
Пример:
Стандартный ввод:
101010101
Вывод:
4
Ввод:
101001
Вывод:
0