Beseda je morilska, če je k-ponovitev, hkrati pa noben njen strnjeni podniz (razen praznega niza in cele besede) ni k-ponovitev.
Recimo, da lahko pri sestavljanju besed uporabljamo le prvih m malih črk angleške abecede. Zanima nas, koliko morilskih besed dolžine vsaj 1 in največ n se da pri teh omejitvah sestaviti.
Vhodni podatki
V prvi vrstici je eno celo število T, tj. število testnih primerov. Sledijo testni primeri; vsak je v svoji vrstici, v njej pa so tri cela števila, ločena s po enim presledkom: naprej m, nato k in nazadnje n.
Omejitve vhodnih podatkov
- 1≤T≤20
- 1≤m≤18
- 2≤k≤5
- 1≤n≤22
Izhodni podatki
Za vsak testni primer izpišite po eno vrstico, v njej pa naj bo eno samo celo število, namreč število morilskih besed, ki se jih da sestaviti pri danih m, n in k.
Omejitve izhodnih podatkov
Omejitve vhodnih podatkov zagotavljajo, da odgovor, po katerem sprašuje naloga, zagotovo ne bo večji od 1015.
Primer vhoda
Koda: Izberi vse
2
2 4 8
3 3 7
Pripadajoč izhod
Koda: Izberi vse
4
9
Komentar
Pri prvem testnem primeru so na primer možne naslednje štiri morilske besede: aaaa, bbbb, abababab in babababa.