Az S. 151. feladat (2021. március)

S. 151. Egy versenyen $\displaystyle N$ diák vett részt, minden versenyzőnek $\displaystyle N$ feladatot kellett megoldana. A diákok minden feladatra egy 1 és $\displaystyle K$ közötti egész számot kaptak értékelésként. A versenybizottság egy $\displaystyle N$ sorból és $\displaystyle N$ oszlopból álló táblázatban összegyűjtötte az összes diák összes feladatának értékelését. Az $\displaystyle i$-edik sor az $\displaystyle i$-edik diák megoldásaira kapott pontokat tartalmazza, a $\displaystyle j$-edik oszlop a $\displaystyle j$-edik feladatra beküldött megoldások értékelését tartalmazza. Ha egy diák egy feladatra nem küldött be megoldást, akkor ott a 0 szám szerepel.

A versenybizottság észrevette, hogy minden feladathoz találhatunk legalább egy olyan diákot, aki nem oldotta meg a feladatot, és minden diákhoz találhatunk legalább egy olyan feladatot, amelyet az adott diák nem oldott meg. Vagyis a táblázat minden oszlopában és minden sorában szerepel legalább egy 0 érték.

Adjuk meg, hogy hány különböző értékelő táblázat lehet (két táblázat különböző, ha van legalább egy elemük, amelyben különböznek). A táblázatok száma nagyon nagy is lehet, ezért a szám $\displaystyle 10^{9}+7$-tel vett osztási maradékát adjuk meg.

Bemenet: az első sor tartalmazza a szóközzel elválasztott $\displaystyle N$ és $\displaystyle K$ számokat.

Kimenet: adjuk meg a lehetséges táblázatok számát modulo $\displaystyle 10^{9}+7$.

Lehetséges táblázatok $\displaystyle N=2$ és $\displaystyle K=1$ esetén:

Korlátok: $\displaystyle 2\le N \le {10}^{5}$, $\displaystyle 2\le K\le {10}^{9}$. Időkorlát: 0,4 mp.

Értékelés: a pontok 40%-a kapható, ha $\displaystyle N \le 100$. További 40% kapható, ha $\displaystyle N \le 5000$.

Beküldendő egy s151.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2021. április 15-én LEJÁRT.

A feladat megoldásához 2D-s logikai szitára volt szükség, amivel egy egyszerű négyzetes megoldást kaphatunk.

Innen matematikai azonosságok és gyorshatványozás segítségével gyorsabb megoldást kaphatunk.

Részletes leírás Varga Péter megoldásában:

VargaPeter.docx

Statisztika:

3 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Kovács Alex, Varga 256 Péter.

A KöMaL 2021. márciusi informatika feladatai