B — Találó elnevezés

Forrás: Pexels

A minap azon gondolkodtam a székemen ülve, hogy „melyik a legjobb (best) tétel?” A kedvenc keresőmmel (Ask Jeeves) eltöltött 1 óra után rábukkantam a BEST tételre. (A BEST tétel az irányított gráfokban lévő Euler-körök számának meghatározására ad egy formulát; bár ez nem lényeges ebben a feladatban.) A BEST tétel a cikk szerzőiről kapta a nevét: de Bruijn, van Aardenne-Ehrenfest, Smith és Tutte.

Egy elnevezést találónak nevezünk, ha előáll úgy, hogy mindegyik szerző nevéből kiválasztunk egy nagybetűt (tetszőleges sorrendben). Vegyük észre, hogy a fentiek alapján az elnevezés betűinek száma meg kell, hogy egyezzen a szerzők számával.

A dél-csendes-óceáni régió feladatkiírói tavaly bebizonyítottak egy tételt a k-adik hatványmaradékok számáról modulo n, és most szeretnénk ennek a tételnek egy találó nevet adni. A feladatkiírók nevei a következők: Anderson, Best, Cameron-Jones, Corney, French, Guttmann, Haigh, Lobb, Sergeev, Tran, Ward-Graham és Whalan. Sajnos bár az „ABCCFGHLSTWW tétel” tartalmaz egy-egy betűt mindegyik szerző nevéből, az ABCCFGHLSTWW nem egy érvényes szó (a valóságban az angol szavakat tekintjük érvényesnek; ebben a feladatban viszont megadjuk az érvényes szavak halmazát). Ráadásul akárhogy is permutáljuk a neveket, nem tudunk érvényes szót formálni a feladatkiírók neveiben szereplő nagybetűkből. Azonban ha csak Anderson, French, Sergeev és Tran jegyeznének egy tételt, akkor azt hívhatnák FAST tételnek (French, Anderson, Sergeev és Tran). Érdekes módon ez az egyetlen olyan permutációja ezeknek a neveknek, amelyből kijön a FAST tétel. Ha ezzel szemben a szerzőket Merlinnek, Oberonnak és Othellónak hívnák, akik a tételüket MOO tételnek szeretnék nevezni, akkor két olyan permutációja is létezne a neveiknek (Merlin, Oberon és Othello, valamint Merlin, Othello és Oberon), amelyek találóvá tennék a MOO tétel elnevezést.

Egy tétel publikációja esetén a nevek sorrendje általában fontos. Mivel azonban nekem már megvan az oktatói kinevezésem, engem mindössze az érdekel, hogy meghatározzam azoknak a permutációknak a számát, amelyek találóvá tesznek egy elnevezést. Egy tétel szerzőinek és a tétel érvényes elnevezéseinek az ismeretében határozd meg a szerzőnevek azon permutációinak a számát, amelyek találóvá teszik az egyes elnevezéseket!

A bemenet specifikációja

A bemenet egy olyan sorral kezdődik, amelyben két egész szám szerepel: n (1 ≤ n ≤ 10), a szerzők száma, és k (1 ≤ k ≤ 1 000), az érvényes szavak száma.

A következő n sorban a szerzők nevei következnek, mindegyik sorban egy-egy. A szerzőnevek csak angol kis- és nagybetűkből állnak, és legalább 1, legfeljebb 20 karakter hosszúságúak. Minden szerzőnév tartalmaz legalább egy nagybetűt.

A következő k sor az érvényes szavakat tartalmazza, soronként egyet-egyet. Az érvényes szavak kizárólag angol nagybetűkből állnak, és legalább 1, legfeljebb 20 karakter hosszúságúak.

A kimenet specifikációja

A kimenetre k darab egész számot kell kiírni (mindegyiket külön sorban), amelyek az egyes elnevezésekhez tartozó érvényes szerzőnév-permutációk számát tartalmazzák.