Проблема с интервью (проблема с раскрашиванием сетки для больших входов)

Question

Недавно я давал тест на хакерранк для какой-то компании и натолкнулся на следующий вопрос. Я искал и обнаружил, что это неразрешимо (NP-hard) для данного ограничения. Пожалуйста, дайте мне знать, если вы знаете, как решить эту проблему.

Задача

Рассчитайте количество способов покрасить сетку N * M, используя K цветов. Соседние квадраты в сетке должны иметь разные цвета. Квадраты считаются смежными, если они имеют общее ребро.

Ограничение: 1 <= N, W, K <= 10 ^ 5. Попросили напечатать ответ, полученный выше, после использования его мода с 10 ^ 9 +7 </p>

Спасибо

Answer 1

В соответствии с решением, которое я нашел здесь, есть подробное объяснение вопроса, размещенного в обмене стека jernej. Размещение ссылки ниже.

проблема Рида и Тутте. По сути, вы запрашиваете хроматический c полином графа сетки (вершины степени 1 не имеют значения.) См. Прилагаемую картинку из Read R. C. и WT Tutte. Хроматы c полиномы. В: LW Beineke и RJ Wilson, Избранные темы в теории графов, том 3, страницы 15--42.