Задача 415
Титанические множества

Множество точек единичной решетки S называется титаническим множеством, если сущетсвует прямая, проходящая через ровно две точки этого множества.

Примером титанического множества является S = {(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0)}, где прямая, проходящая через (0, 1) и (2, 0), не проходит через ни одну другую точку множества S.

Множество {(0, 0), (1, 1), (2, 2), (4, 4)}, напротив, титаническим не является, потому что прямая, проходящая через любые две точки этого множества, также проходит и через две другие точки.

Для любого положительного целого N пусть T(N) будет количеством титанических множеств S, каждая точка (x, y) которого удовлетворяет 0 ≤ x, yN. Можно показать, что T(1) = 11, T(2) = 494, T(4) = 33554178, T(111) mod 108 = 13500401 и T(105) mod 108 = 63259062.

Найдите T(1011) mod 108.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net