Zadanie

Neviem, či si to viete predstaviť, ale život takéto Krtka vôbec nie je jednoduchý. Krtko má viacero úloh, ktoré musí spraviť. Napr. vykopať tunel, rozryť nejakú záhradu, natočiť nové diely Krtka, pripraviť niekoľko sústredení a v neposlednom rade napísať bakalárku. Nie je to také jednoduché, ale keďže Krtko sa snaží pristupovať ku všetkým úlohám férovo, priradil každej úlohe nejakú prioritu. Navyše chce, aby pre každé dve úlohy platilo, že dôležitej z nich venuje viac času. Krtka teraz zaujíma koľkými spôsobmi vie rozdeliť svoj čas medzi jeho úlohy. Keďže táto úloha nie je medzi Krtkovými, musíte ju vyriešiť vy.

Úloha

Krtko má \(n\) úloh a \(m\) času. Tento čas chce (celý) rozdeliť medzi tieto úlohy tak, aby dôležitejšia úloha dostala viac času. Žiadne dve úlohy nie sú rovnako dôležité. Vašou úlohou je vypočítať, koľkými spôsobmi sa to dá urobiť. Keďže Krtkovi sa z veľkých čísel točí hlava, vypíšte toto číslo modulo \(10^9+7\) (\(1\,000\,000\,007\)).

Formát vstupu

Na jedinom riadku vstupu sú čísla \(n\) a \(m\) - počet úloh, ktoré má Krtko, a čas, ktorý chce celý Krtko úlohám venovať.

Formát výstupu

Vypíšte jedno číslo - počet spôsobov, koľkými krtko dokáže rozdeliť svoj čas medzi zadané úlohy. Keďže toto číslo môže byť veľmi veľké, vypíšte ho modulo \(10^9+7\).

Hodnotenie

V každej sade platí, že \(0 \leq n \leq 100\), \(1 \leq m < 50\,000\)

Príklady

Input:

2 4

Output:

2

Buď rozdelí čas medzi úlohy ako 0 a 4, alebo ako 1 a 3. Menej dôležitej úlohe nemôže venovať 2 alebo viac času, lebo potom by dôležitejšej úlohe nemohol venovať viac času ako menej dôležitej (teda viac ako 2).

Prvá vec, ktorú si môžeme uvedomiť, je koľko najmenej času potrebujeme na \(n\) úloh. Najmenej času, ktorý vieme venovať najmenej dôležitej úlohe je \(0\). Potom najmenej času ktorý vieme venovať druhej najmenej dôležitej úlohe je 1. Vo všeobecnosti vieme povedať, že ak máme \(i\)-tu najmenej dôležitú úlohu, musíme jej venovať aspoň \(i-1\) času. Každej z i-1 menej dôležitých úloh musíme totiž venovať iný čas. \(n\) úlohám teda musíme venovať aspoň \(0 + 1 + 2 + ... + (n-1) = \frac{(n-1)\cdot n}{2}\)

Keď už vieme koľko času najmenej musíme venovať ktorej úlohe, môžeme problém zo zadania mierne upraviť. Zvyšný čas, teda \(m - \frac{(n-1)\cdot n}{2}\) chceme rozdeliť medzi \(n\) úloh tak, aby dôležitejšia dostala viac alebo rovnako ako menej dôležitá. To môže pôsobiť ako zbytočné, no povedie to ku kúsok jednoduchšej implementácií.

Riešenie

Túto úlohu budeme riešiť pomocou dynamického programovania. Cheme zistiť, ako sa dá rozdeliť čas medzi nejaké úlohy. Prvým riešením by mohlo byť, že vyskúšame všetky možnosti koľko času môžeme venovať najmenej dôležitej úlohe, a zvyšok je podobná otázka - o jednu úlohu menej a o nejaký čas menej. Možeme si všimnúť, že ak sa rozhodneme venovať najmenej dôležitej úlohe \(k\) času, musíme aj každej ďaľšej úlohe venovať aspoň \(k\) času. Počet možností teda môžeme spočítať ako \(f(u, c) = \sum f(u-1,\ c-u\cdot k)\), kde \(f(u, c)\) je počet možností ako vieme rozdeliť medzi \(u\) úloh \(c\) času. Samozrejme využijeme memoizáciu, aby sme jednu hodnotu nepočítali viackrát.

Takéto riešenie prejde všetky možnosti ako vieme rozdeliť čas medzi úlohy. Pozrime sa na zložitosti. Máme \(n \cdot m\) stavov, každý vieme spočítať v \(O(m)\). Výsledná zložitosť teda bude \(O(nm^2)\).

Vzorové riešenie

V predošlom riešení sme sa vždy rozhodli koľko presne času budeme venovať jednej úlohe, čo viedlo k tomu, že jeden stav sme museli počítať až v zložitosti \(O(m)\). V tomto riešení to vylepšíme. Vždy sa rozhodneme, či najmenej dôležitej úlohe ešte budeme pridávať čas, alebo už nie. Presnejšie sa rozhodneme či pridáme ešte \(1\) čas. Opakovaným pridávaním \(1\) času vieme pridať ľubovoľne veľa. Ak čas pridáme, musíme ho pridať aj všetkým ostatným úlohám, podobne ako v minulom riešení. Bude teda platiť, že \(f(u, c) = f(u,\ c-u) + f(u-1, c)\). Počet rôznych stavov, ktoré potrebujeme spočítať sa nezmenil, ale každý už vieme vypočítať v \(O(1)\). Preto celková časová zložitosť našeho algoritmu bude \(O(nm)\) a pamäťová \(O(nm)\).

Táto pamäťová zložitosť sa dá ešte zlepšiť. Predstavme si, že máme iteratívne naprogramovaný náš algoritmus. Teda máme dvojrozmerné pole, a postupne ho vypĺňame hodnotami \(f(u, c)\). Všimnime si, že keď dopĺňame riadok pre nejaké \(u\), nepotrebujeme si pamätať celú tabuľku, ale stačí nám posledný a aktuálny riadok - teda tie, pre \(u\) a \(u-1\). Takto vieme zmenšiť pamäťovú zložitosť na \(O(m)\).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.