{"problem":{"name":"H. Рудольф и забор","description":{"content":"Как-то раз, проснувшись с утра и обнаружив, что у него украли дом, Рудольф понял, что ему необходимо защитить свой участок от подобных вторжений. Он решил построить забор и для этого закупил в строите","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10132H"},"statements":[{"statement_type":"Markdown","content":"Как-то раз, проснувшись с утра и обнаружив, что у него украли дом, Рудольф понял, что ему необходимо защитить свой участок от подобных вторжений. Он решил построить забор и для этого закупил в строительном магазине доски. Когда он вернулся из магазина и осмотрел свою покупку, он понял, что не все доски имеют одинаковую длину. Тогда Рудольф решил выйти из ситуации самым очевидным образом, а именно — построить симметричный забор.\n\nЗабор из n досок Рудольф считает симметричным, если доски в позициях i и (n - i + 1), где , имеют равные высоты.\n\nКо всему прочему Рудольф хочет, чтобы его забор имел максимальную длину. Однако, он внезапно осознал, что способов построить такой забор может быть очень много, и попросил вас помочь ему подсчитать их количество. Два способа построения забора считаются различными, если высоты досок отличаются хотя бы в одной позиции.\n\nПомогите Рудольфу узнать ответ на его вопрос.\n\nПервая строка содержит целое число n (1 ≤ n ≤ 105) — количество досок у Рудольфа.\n\nВторая строка содержит n целых чисел hi (1 ≤ hi ≤ 1018) — высоту каждой из досок.\n\nВыведите одно целое число — количество различных способов составить симметричный забор максимальной длины из имеющихся у Рудольфа досок. Так как это количество может оказаться достаточно большим, выведите остаток от его деления на (109 + 9).\n\nВ первом примере существуют два способа составления симметричного забора из всех имеющихся досок: (1, 2, 2, 2, 1) и (2, 1, 2, 1, 2).\n\nВо втором примере для получения максимально длинного забора мы можем задействовать только 5 досок и составить следующие симметричные заборы: (1, 2, 1, 2, 1), (1, 2, 3, 2, 1), (2, 1, 1, 1, 2), (2, 1, 3, 1, 2).\n\n## Входные Данные\n\nПервая строка содержит целое число n (1 ≤ n ≤ 105) — количество досок у Рудольфа.Вторая строка содержит n целых чисел hi (1 ≤ hi ≤ 1018) — высоту каждой из досок.\n\n## Выходные Данные\n\nВыведите одно целое число — количество различных способов составить симметричный забор максимальной длины из имеющихся у Рудольфа досок. Так как это количество может оказаться достаточно большим, выведите остаток от его деления на (109 + 9).\n\n## Примеры\n\nВходные данные52 1 2 2 1Выходные данные2Входные данные61 3 2 2 1 1Выходные данные4\n\n## Примечание\n\nВ первом примере существуют два способа составления симметричного забора из всех имеющихся досок: (1, 2, 2, 2, 1) и (2, 1, 2, 1, 2).Во втором примере для получения максимально длинного забора мы можем задействовать только 5 досок и составить следующие симметричные заборы: (1, 2, 1, 2, 1), (1, 2, 3, 2, 1), (2, 1, 1, 1, 2), (2, 1, 3, 1, 2).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of boards.  \nLet $ H = (h_1, h_2, \\dots, h_n) $ be a sequence of integers representing the heights of the boards.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq h_i \\leq 10^{18} $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFind the number of distinct symmetric fences of **maximum possible length** that can be constructed using a subset of the boards, where a fence of length $ \\ell $ is symmetric if for all $ i \\in \\{1, \\dots, \\lfloor \\ell/2 \\rfloor\\} $, the height at position $ i $ equals the height at position $ \\ell - i + 1 $.  \n\nTwo fences are distinct if their height sequences differ in at least one position.  \n\nOutput the count modulo $ 10^9 + 9 $.  \n\n**Key Insight**  \nThe maximum length $ \\ell $ of a symmetric fence is determined by the maximum number of boards that can be paired symmetrically (with possibly one unpaired center board). For each distinct height $ v $, let $ c_v $ be its frequency in $ H $.  \n\nTo maximize $ \\ell $:  \n- For each $ v $, we can use at most $ \\left\\lfloor \\frac{c_v}{2} \\right\\rfloor $ pairs.  \n- Let $ P = \\sum_v \\left\\lfloor \\frac{c_v}{2} \\right\\rfloor $ be the total number of usable pairs.  \n- Then maximum fence length is $ \\ell = 2P + r $, where $ r = 1 $ if there exists at least one $ v $ with $ c_v $ odd, else $ r = 0 $.  \n\nThe number of distinct symmetric fences of length $ \\ell $ is:  \n- If $ r = 1 $: choose **one** center height from all $ v $ with odd $ c_v $, and assign the $ P $ pairs to the $ P $ symmetric positions.  \n- The number of ways to assign the pairs is the multinomial coefficient:  \n$$\n\\frac{P!}{\\prod_v \\left( \\left\\lfloor \\frac{c_v}{2} \\right\\rfloor ! \\right)}\n$$  \n- Multiply by the number of choices for the center: $ \\#\\{ v \\mid c_v \\text{ is odd} \\} $.  \n\nIf $ r = 0 $: no center, so only the multinomial coefficient.  \n\nThus, the answer is:  \n$$\n\\left( \\#\\{ v \\mid c_v \\text{ odd} \\} \\right)^r \\cdot \\frac{P!}{\\prod_v \\left( \\left\\lfloor \\frac{c_v}{2} \\right\\rfloor ! \\right)} \\mod (10^9 + 9)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10132H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}