10-11 класс


Есеп C. Хан және тізбек

Ограничение по времени:
2 seconds
Ограничение по памяти:
512 megabytes

Хан туған күніне орай $n$ саннан тұратын сан тізбегін сыйлық ретінде алып, онымен ойнай бастады. Ол тізбектің әр санын алып, оны $m$ рет жазды. Сонымен қатар, Ханның сүйікті жай саны $P$ бар. Оны ендігі қызықтыратыны, осы тізбектің неше тізбекшесінің қосындысы $P$ санына бөлінетіндігі. Ханға осыны анықтауға көмектесіңіз.
Формат входного файла
Бірінші жолда бос орын арқылы үш бүтін сан $n$, $m$, $P$ берілген — сәйкесінше Ханның тізбегінің ұзындығы, әр санды неше рет жазатын мөлшері және жай сан $(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3)$. Екінші жолда бос орын арқылы $n$ сан $a_1, a_2, ..., a_n$ берілген — Хан сыйлық ретінде алған тізбек $(1 <= a_i <= 10^9)$.
Формат выходного файла
Бір сан шығарыңыз — қосындысы $P$-ға бөлінетін тізбекшелердің саны. Бұл сан өте үлкен болуы мүмкін болғандықтан, $1000000007$-ге бөлгендегі қалдығын шығарыңыз.
Система оценки
1-бөлім (10 ұпай) — $ n <= 10^5$, $m <= 10^5,$ $P = 2 $. 2-бөлім (10 ұпай) — $ n * m <= 20$, $P <= 1000 $. \par 3-бөлім (10 ұпай) — $ n * m * P <= 10^6, $. \par 4-бөлім (20 ұпай) — $ n * m <= 250000$, $P <= 500 $. \par 5-бөлім (50 ұпай) — $ n <= 10^5$, $m <= 10^9$, $P <= 1000 $.
Пример:
\exmpfile{example.01}{example.01.a}%
Замечание
Хан бастапқы тізбекті былай түрлендіреді. Бастапқы тізбек $a_1, a_2, ..., a_n$ болсын. Және де бос $b$ тізбегі болсын делік. Бір-бірден, солдан оңға қарай $a$ тізбегінен сандарды алып, $a_i$ санын $b$ тізбегінің артына $m$ рет тіркестіріп жазайық. Хан есепті жаңадан пайда болған $b$ тізбегімен шығарады. Тізбекше — бастапқы тізбектің бірнеше, мүмкін нөл, элементін өшіріп тастағаннан кейінгі қалған тізбек. Бірінші мысалда, $b$ тізбегі мынадай болады: $3, 3, 7, 7, 4, 4$. Есептің жауабында көрсетілгендей, $11$ тізбекшенің қосындысы $5$-ке бөлінеді. Олар мыналар: $[3, 7]$, $[3, 7]$, $[3, 7]$, $[3, 7]$, $[3, 3, 4]$, $[3, 3, 4]$, $[3, 3, 7, 7]$, $[7, 4, 4]$, $[7, 4, 4], $[3, 7, 7, 4, 4], $[3, 7, 7, 4, 4]$. ( Nurdaulet Akhanov )
посмотреть в олимпиаде

Комментарий/решение:

  0
2021-02-15 11:57:52.0 #

кодты корсету/жасыру

ZyMa
пред. Правка 3   0
2021-02-21 18:30:10.0 #

import itertools

input = open("test_in.txt", "r")

output = open("test_out.txt", "w")

⠀

n,m,p = map(int, input.readline().split())

a = input.readline().split()

b = []

q = 0

⠀

for i in a:

⠀⠀⠀⠀for r in range(m):

⠀⠀⠀⠀⠀⠀⠀b.append(int(i))

⠀

for L in range(1, len(b)+1):

⠀for k in itertools.combinations(b, L):

⠀⠀⠀if sum(k)%5==0:

⠀⠀⠀⠀⠀⠀⠀q+=1

⠀⠀⠀⠀⠀⠀⠀#print(k) 5-ке бөлінетін комбинацияларды шығару үшін

⠀

output.write(str(q))

input.close()

output.close()

Nurmukhammet