ЗАДАНИЕ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ!!! ПОМОГИТЕ СРОЧНО1111.
ЗАДАНИЕ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ!!! ПОМОГИТЕ СРОЧНО1111.
Для решения данной задачи можно использовать динамическое программирование.
Создадим двумерный массив dp размером (N+1) x K, где dp[i][j] будет хранить количество способов выбрать варианты ответов на первые i вопросов так, чтобы сумма вариантов делилась на j.
Инициализируем массив dp нулями, кроме dp[0][0] = 1, так как для выбора нулевых вариантов ответов сумма будет равна нулю и делится на любое число.
Затем заполним массив dp построчно. Для каждого вопроса i и каждого возможного значения суммы j от 0 до K-1, будем перебирать все варианты ответов на i-ый вопрос и обновлять значения dp[i][j] следующим образом:
dp[i][j] = (dp[i][j] + dp[i-1][(j - a[i]) % K]) % (10^9 + 7)
где a[i] - количество вариантов ответов на i-ый вопрос.
После заполнения массива dp, ответом на задачу будет сумма всех значений dp[N][0], dp[N][K], dp[N][2K], ..., dp[N][(K-1)K].
Вот реализация данного алгоритма на языке Python:
N, K = map(int, input().split())
a = [int(x) for x in input().split()]
dp = [[0] * K for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
for j in range(K):
for k in range(a[i-1]):
dp[i][(j + k) % K] = (dp[i][(j + k) % K] + dp[i-1][j]) % (10**9 + 7)
answer = sum(dp[N][k] for k in range(0, K, K))
print(answer % (10**9 + 7))
Этот код решает задачу за время O(NK^2) и использует O(NK) дополнительной памяти.