Ну тогда про это стоило написать. Давайте тогда не писать здесь ничего по задачи, пока не будет комментариев snarknews.

Upd.

Снарк говорит, что можно обсуждать.

Пусть есть матрица с единицами. Возьмём главую диагональ, и умножим все её клетки на какое-то простое число. Сдвинем по циклу, умножим ещё раз, и так N раз.

2  3  5  7 11
11 2  3  5  7 
7 11  2  3  5
5  7 11  2  3
3  5  7 11  2

Если N нечетное то можно сделать такой же квадрат для побочной диагонали но с другими простыми числами.

13 17 19 23 29
17 19 23 29 13
19 23 29 13 17
23 29 13 17 19
29 13 17 19 23

Если перемножить квадраты то все числа будут разные, т.к. каждое число однозначно определяется двумя диагоналями на которых оно лежит.

Для чётных N так не выйдет, поэтому в первом квадрате я сдвигал нижнюю половину матрицы:

i<n/2 : j=i
i>=n/2 : j = n/2 + (i-n/2+1)%(n/2)
2   3  5  7 11 13
13  2  3  5  7 11
11 13  2  3  5  7
5  7  11 13  2  3
3  5  7  11 13  2
7  11 13  2  3  5

После этого клетка опять однозначно определялась по двум диагоналям, а значит все числа были разные.

L:

Положим в мапу все цифры со значением 1. Потом (n - 1) раз сделаем следующее: вынем каждое число из мапы, умножим на каждую цифру и положим обратно. Потом пройдёмся по всем значениям в мапе, возведём в квадрат и прибавим к ответу.

Код

N:

Вроде такое должно работать:

Пройдёмся массиву от B влево и будем поддерживать разность (количество чисел меньше B — количество чисел больше B). Затем пройдёмся от B вправо поддерживая ту же разность. На каждом элементе прибавим к ответу количество раз, которое текущая разность с противоположным знаком встретилась пока проходились влево.

UPDATE: Наконец таки появилась дорешка. Это решение зашло. Код.

Решения нет только в случае всех одинаковых букв.

UPD. Иначе возьмём обычную цепочку и двумя разными способами заменим одно ребро на цикл (например, для cтроки aabb автоматы будут aa*bb и aabb*).

У нас biginteger, так что вряд ли.

В задаче А весьма приятная геометрия — благодаря ограничению "никакие 3 точки не лежат на одной прямой" не вылазит никаких корнеркейсов. Фиксируем форт, для него сортируем все башни и дроны по углу, дальше два указателя. При фиксированном форте и фиксированной левой башне второй указатель говорит нам о том, где оканчивается валидный отрезок башен (т.е. какая последняя башня такая, что стена между этой башней и левой башней будет перед фортом, а не позади него), а количество подходящих пар "дрон-башня" на этом отрезке можно вычислять за О(1), если предварительно посчитать различные частичные суммы вроде числа башен на префиксе, числа дронов на префиксе, числа дронов перед башнями и т.д.

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

Наш код: http://ideone.com/KzB2UD

B:

The task is obviously redused to the following: we have some string S, how many ways to add x characters to it and get borderless word?

Let's calculate the same thing for not borderless words and then subtract it from 2^x.

To do it one can iterate over L — the minimal length of such suffix that corresponds prefix. Now we need to know that there will be no such suffix with less length -- it's exactly our initial task with less x.

They are there now.

http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=9915