Допустим, m = 7, n = 3, A = [4, 2, 5].

Условимся, что произведение пустого множества — единица. Изначально доступно лишь одно состояние динамики: dp[1] = true.

Перебираем массив А.

Для первого элемента: 1 * 4 % 7 = 4, значит dp[4] = true.

Для второго элемента: 1 * 2 % 7 = 2, 4 * 2 % 7 = 1, значит dp[2] = true, а dp[1] и так было true до этого.

Для третьего элемента: 1 * 5 % 7 = 5, 2 * 5 % 7 = 3, 4 * 5 % 7 = 6, значит dp[5] = true, dp[3] = true, dp[6] = true.

Максимальным произведением по модулю m получилось 6.

Для восстановления ответа в динамике нужно так же хранить число, с помощью которого пришли в это состояние, и для упрощения — состояние из которого пришли.

Для описанного теста это будет выглядеть так (с помощью какого числа пришли/откуда пришли):

dp[1] = { -, - } dp[2] = { 2, 1 } dp[3] = { 5, 2 }

dp[4] = { 4, 1 } dp[5] = { 5, 1 } dp[6] = { 5, 4 }

Определив максимальное достаточно лишь пройтись в обратную сторону по состояниям динамики до единицы.

То есть для описанного теста: 6 -> 4 -> 1, а сам ответ: 5 * 4.

Это ничего, потому что описанное решение работает за O(n*m).