Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Свет је коначно постао једно мирно место, пуно среће и љубави. Како би успела да се супроставе крагујевачком фудбалском гиганту, два мала фудбалска клуба Партизан и Црвена звезда су се ујединили у један и постали Црно Бела Звезда. Након уједињења, Црно Бела Звезда је добила нови грб. Грб је у облику црно белог звезда графа са \(4\) чвора. Црно бели звезда граф са \(4\) чвора предстаља стабло чији су сви чворови обојени црном или белом бојом и чији је корен обојен супротном бојом од листова (ако је корен обојен црном бојом онда су листови обојени белом, док ако је корен обојен белом бојом листови су обојени црном).
Млади Ћими, вођа навијача Црно Беле Звезде, добио је црвени папир на коме су нацртане црне и беле тачке. Нацртано је тачно \(N\) тачака нумерисаних бројевима од \(1\) до \(N\). Боје тачака су одређене низом \(А\), ако је \(i\)-та тачка бела онда је \(А_i = 0\), у супортном \(А_i = 1\). Kaда би се тачке спојиле редом \(1 -> 2 -> \dots -> N -> 1\), градиле би правилан \(N\)-тоугао. Ћими је просто опседнут грбом новог клуба и жели да га нацрта тачно \(\frac{N}{4}\) пута на том црвеном папиру. Он жели да свака тачка припада тачно једном грбу и да се грбови међусобно не пресецају, јер мисли да би тако урушио лепоту грбова.
Ћими вас је замолио да му помогнете да израчуна број начина да нацрта тачно \(\frac{N}{4}\) грбова. Два начина се разликују ако постоји бар један грб који је нацртан на једном цртежу и није нацртан на другом. Како број начина може бити велики, исписати тај број по модулу \(10^9 + 7\).
Потребно је да имплементирате функцију:
\(N\) је број тачака на папиру. \(А\) је низ дужине \(N\) који представља боје тачака, \(i\)-та тачка је бела ако важи \(А_i = 0\), иначе је тачка црна и \(А_i = 1\). ** Низ \(А\) је индексиран од \(1\) .**
Функција треба да врати цео број \(X\) – број начина да Ћими нацрта грбове по модулу \(10^9 + 7\).
Нека је \(N = 8\), \(A = [1, 1, 0, 1, 0, 1, 1, 1]\).
Постоји \(2\) начина да се нацртају звезде:
Постоји укупно \(14\) подзадатака, који задовољавају ограничења написана у табели:
| Редни број подзадатка | Ограничење за N | Број поена |
|---|---|---|
| 1 | 12 | 4 |
| 2 | 24 | 4 |
| 3 | 52 | 4 |
| 4 | 76 | 4 |
| 5 | 100 | 4 |
| 6 | 128 | 5 |
| 7 | 152 | 5 |
| 8 | 200 | 5 |
| 9 | 252 | 5 |
| 10 | 300 | 12 |
| 11 | 352 | 12 |
| 12 | 400 | 12 |
| 13 | 452 | 12 |
| 14 | 500 | 12 |
Потребно је да пошаљете тачно један фајл zvezda.cpp,
који имплементира поменуту функцију. Осим тражене функције, ваш фајл
може садржати и додатне глобалне променљиве, помоћне функције и додатне
библиотеке.
Ваша функција мора бити следећег облика:
int Zvezda(int N, int *A);
Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.
Уз задатак, обезбеђен вам је “template” фајл code.cpp
који можете користити и мењати по потреби. Такође вам је обезбеђен
програм grader.cpp који служи да лакше тестирате кодове.
Овај програм учитава са стандардног улаза следеће податке:
Затим овај програм зове вашу функцију и штампа вредност коју је функција вратила. Кодове ових програма можете мењати по потреби.