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