Кожен шлях містить рівно \(n - 1\)
літер D та \(m - 1\) літер
R, бо саме стільки разів фішка мусить рухатися вниз і
праворуч відповідно. Тож, порахувавши кількість D і
R у будь-якому з рядків, отримаємо \(n = \texttt{кількість D} + 1\), \(m = \texttt{кількість R} + 1\)
Якщо \(n = 2\), дозволені лише квадрати \(1 \times 1\), їх 4, тож виграє другий гравець.
Якщо \(n \ge 3\), перший гравець зафарбовує центральний квадрат розміром \((n - 2) \times (n - 2)\). Після цього залишаються лише клітинки, по краях, де можна розміщувати квадрати \(1 \times 1\), і їх парна кількість — тож перший гравець гарантовано виграє.
C. Операції зі стовпцями та літерою Г
Усі операції по суті інвертують значення в певних клітинках. Якщо якусь операцію (наприклад, інверсію одного й того самого стовпця) застосовано непарну кількість разів — ефект такий, ніби її виконали один раз; якщо парну — нічого не змінилося.
Операція у формі літери Г не зачіпає правий нижній елемент, тож змінити його можна лише інверсією останнього стовпця. Спершу визначаємо, чи потрібно це робити, а потім, обробляючи знизу вгору, виправляємо значення у цьому стовпці за допомогою операцій-Г.
Процес повторюємо для кожного стовпця, рухаючись справа наліво.
Зрештою, залишиться лише перший стовпець. Оскільки операції-Г на нього
більше не діють, перевіряємо, чи всі значення однакові. Якщо так —
інверсією першого стовпця зможемо їх обнулити, отже відповідь
Yes.
Для \(n\) від 2 до 7 дерево у вигляді ланцюга дає максимальну відповідь.
Для парних \(n > 7\) не можна отримати більшу відповідь, ніж \(\frac{n}{2} - 1\). Ми можемо отримати рівно таке значення лише для парних \(n\) за допомогою конструкції, зображеної на Рис. 1.
Для непарного \(n > 7\) максимально можлива відповідь рівна \(\lfloor \frac{n - 2}{3} \rfloor\). На рисунку 2 зображена конструкція, що при \(cnt = \lfloor \frac{n - 2}{3} \rfloor\) досягає шуканої відповіді.
Розглянемо квадрат з кутами в точках \((-10^9, -10^9)\) та \((10^9, 10^9)\). Якщо по такому квадрату рухати точку до сусідньої, наприклад, проти годинникової стрілки, то відповідь на такий запит або не зміниться, або збільшить номер вершини на 1 (тут вважаємо, що вершина 1 та \(n + 1\) — це те ж саме). Отже, ми таким чином зможемо знайти шукану точку.
Запитаємось номер найдальшої точки до \((-10^9, -10^9)\) та \((10^9, 10^9)\). Можна показати, що значення для цих точок буде різне, а отже ми можемо визначити, в якій половині периметру квадрату є шукана точка. Ну і на відповідному проміжку ми можемо використати двійковий пошук. Якщо відповідь для точки \((-10^9, -10^9)\) менше за номер точки \((10^9, 10^9)\), то шукана точка знаходиться на лівій або верхній стороні квадрату. І відповідно у бінарному пошуку ми можемо використовувати інваріант, що відповідь для лівої точки більша за відповідь для правої (у такому варіанті ми завжди на шляху від більшого досягнемо \(n + 1\), тобто 1).
Будемо розв’язувати задачу за допомогою динаміки: \(dp[i][j]\) — кількість послідовностей довжини \(i\), у яких останній елемент має остачу \(j\) за модулем \(k\). Ми працюємо з остачами, але оскільки числа в послідовності обмежені \(0 \le a_i < m\), можемо попередньо порахувати \(cnt[j]\) — кількість чисел від 0 до \(m - 1\), які дають остачу \(j\) за модулем \(k\).
Розіб’ємо всі остачі \(j\) (від 0 до \(k - 1\)) на групи:
окрема група — \(j = 0\),
класи еквівалентності за парами значень \((cnt[j], cnt[k - j])\).
Можна побачити, що всього таких груп буде не більше чотирьох. Причому для кожної групи значення \(dp[i][j]\) буде однаковим для всіч \(j\) з цієї групи.
Це дозволяє значно скоротити розмірність нашої динаміки: замість відстежування \(k\) різних остач достатньо працювати з 4 значеннями — \(dp[i][t]\), де \(t\) — номер групи.
Останнім кроком перехід із \(dp[i]\) до \(dp[i + 1]\) можна записати як множення на матрицю переходу. Піднесемо її до степеня \(n - 1\), щоб отримати \(dp[n]\) із \(dp[1]\).
Визначимо функцію \(F(pos, n)\), яка визначатиме де закінчить елемент, що починав в позиції \(pos\) в рядку довжини \(n\). Відповідь буде мати такий вигляд:
\(cnt_l\) елементів стоятиме в \(pos_l\)
\(cnt_r\) елементів стоятиме в \(pos_r\)
в кожній клітинці між \(pos_l\) та \(pos_r\) буде рівно по одному елементу
Використавши нашу функцію визначимо \(pos_l = F(1, n)\) та \(pos_r = F(n, n)\). Знайдемо \(cnt_k\) та \(cnt_r\) за допомогою двійкового пошуку та функції \(F\).
Як виглядає функція \(F\)? Заміними
символи L та R на -1 та 1 відповідно.
Визначимо функцію \(G(i)\) як баланс на
префіксі, тобто \(G(i) = \sum_{j = 0}^i
s_j\). Знайдемо останню позицію в рядку, де наш елемент буде біля
однієї з стінок. Якщо такої позиції немає, то до початкової позиції
просто додамо сумарний баланс, інакше така позиція буде або мінімумом,
або максимумом на суфіксі. Випишемо собі цікаві позиції. Перші цікаві
позиції це глобальний мінімум та максмум функції \(G\). Впорядкуємо їх. Після того подивимося
на останню цікаву позицію, якщо це максимум на суфіксі, то наступна
цікава позиція буде мінімумом і навпаки. Шукатимемо наші цікаві позиції,
поки не дойдемо до кінця рядка. У функції \(F\) напишемо двійковий пощук, щоб знайти
останню цікаву позицію, де наш елемент впреться в стінку.