Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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\).

Példa bemenet Példa kimenet
2 17

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.


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