Zadanie

Luxusko si kúpil novú knižku s názvom Kvantové Správanie a Paralelizmus. Dozvedel sa z nej, že (vraj) každé naše rozhodnutie spôsobí vznik paralelných vesmírov, ktoré sú všetky veľmi podobné a líšia sa iba v tom jednom rozhodnutí a v jeho následkoch.

Napríklad, keď sa ráno rozhodnete, či vstanete alebo len zaklapnete budík a pospíte si o 10 minút dlhšie, vzniknú dva paralelné vesmíry. V jednom vesmíre spíte ďalej a pravdepodobne zmeškáte prvú hodinu v škole, v druhom pekne vstanete a prídete do školy načas.

Podľa knižky pri každom takomto rozvetvení vesmíru nastane veľmi slabé chvenie v okolí toho, kto urobil rozhodnutie. Keď sa vesmír rozdvojí, chvenie je zvyčajne také slabé, že sa nedá zachytiť. Je však možné, že ak urobíme rozhodnutie, ktoré má za následok vznik miliardy paralelných vesmírov, spomenuté chvenie sa stane merateľným a celá hypotéza by sa tak dala dokázať.

 

Luxusko teda zobral svoju obrovskú zbierku mincí s hodnotami 1, 5, 10 a 20 centov a vybral sa do obchodu. Kúpi si v obchode niečo v hodnote \(n\) centov, urobí rozhodnutie ako túto vec zaplatí pomocou svojich mincí a napokon svojim vreckovým seizmografom odmeria chvenie.

Potrebuje však namerané výsledky s niečim porovnať, preto chce presne vedieť, koľko vesmírov malo vzniknúť – čiže koľkými spôsobmi sa dá zaplatiť daná suma \(n\).

Úloha

Máte danú cenu \(n\). Zistite, koľkými spôsobmi sa dá táto cena zaplatiť mincami, ktoré majú hodnoty 1, 5, 10 a 20 centov. Dva spôsoby platenia sú rôzne, pokiaľ použijú iný počet kusov nejakej mince.

Výsledok vypíšte modulo \(10^9+7\).

Formát vstupu

Na vstupe je jeden riadok s celým číslom \(n\) (\(1\leq n\leq 10^{18}\)).

Formát výstupu

Vypíšte počet spôsobov, ktorými sa dá zaplatiť suma \(n\) pomocou mincí s hodnotami 1, 5, 10 a 20 modulo \(10^9+7\).

Príklady

Input:

14

Output:

4

Input:

30

Output:

20

Input:

7

Output:

2

Napríklad cenu \(14\) môžeme zaplatiť týmito štyrmi spôsobmi: \(10+1+1+1+1\), \(5+5+1+1+1+1\), \(5+1+1+1+1+1 + 1+1+1+1\) a \(1+1+1+1+1 + 1+1+1+1+1 + 1+1+1+1\)

 

 

 

Označme si \(n_1 = n\), \(n_5 = \lfloor \frac{n}{5} \rfloor\) (t.j. delenie zaokrúhlené nadol), \(n_{10} = \lfloor \frac{n}{10} \rfloor\), \(n_{20} = \lfloor \frac{n}{20} \rfloor\).

Potom vieme, že môžeme použiť najviac \(n_{20}\) dvadsaťcentových mincí, a keď ich použijeme \(i\), tak už môžeme použiť len \(n_{10}-2i\) desaťcentových mincí. A keď tých použijeme \(j\), tak môžeme použiť už len \(n_5-4i-2j\) päťcentových. Zvyšok doplatíme jednocentovými mincami.

Celkový výsledok teda je \[\sum\limits_{i=0}^{(n_{20})} \sum\limits_{j=0}^{(n_{10}-2i)} \sum\limits_{k=0}^{(n_5-4i-2j)} 1\]

Celá úloha je teda o tom, ako spočítať túto sumu čo najrýchlejšie. Použiť tri vnorené cykly by nebol najrýchlejší prístup :) Tak poďme zjednodušovať. Budeme využívať nasledovné vzorce:

Konštanty sa dajú vybrať pred sumu: \(\sum\limits_{i=0}^{n} kf(i) = k\sum\limits_{i=0}^{n} f(i)\)

Suma jednotiek: \(\sum\limits_{i=0}^{n} 1 = n+1\)

Suma tzv. úsečiek: \(\sum\limits_{i=0}^{n} i = \frac{n(n+1)}{2}\)

Suma tzv. štvorcov: \(\sum\limits_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\)

(Všetky 4 vzorce sa dajú pomerne ľahko odvodiť.)

Napríklad vzorec suma jednotiek nám umožňuje spočítať: \(\sum\limits_{k=0}^{n_5-4i-2j} 1 = n_5-4i-2j+1\).

 

Celkový výsledok teda je \(\sum\limits_{i=0}^{(n_{20})} \sum\limits_{j=0}^{(n_{10}-2i)} (n_5-4i-2j+1)\) čím sme si ušetrili jeden forcyklus v programe.

Použitím vzorcov o vyberaní konštánt, vzorca pre súčet jednotiek, a vzorca pre súčet jednotiek dostaneme: \[\sum\limits_{i=0}^{n_{20}} \left( \sum\limits_{j=0}^{(n_{10}-2i)} (n_5-4i+1) + \sum\limits_{j=0}^{(n_{10}-2i)} (-2j) \right)\] sa rovná \[\sum\limits_{i=0}^{n_{20}} \left( (n_{10}-2i+1)(n_5-4i+1) - (n_{10}-2i+1)(n_{10}-2i) \right) \] a to je po úpravách \[\sum\limits_{i=0}^{n_{20}} (n_{10}-2i+1)(n_5-n_{10}+1-2i)\]

Keby ste toto naprogramovali ako forcyklus, už by ste mali 12 bodov z 20.

Ale vieme ísť ešte o krok ďalej, rozpísať si \((n_{10}-2i+1)(n_5-n_{10}+1-2i) = \text{niečo} + \text{niečo}\cdot i + \text{niečo}\cdot i^2\) a vypočítať celú sumu. Ale to už zvládnete sami :).

Takto dostanete algoritmus s časovou zložitosťou \(O(1)\). Na začiatku len spočítate \(n_1\), \(n_5\), \(n_{10}\) a \(n_{20}\), hneď ako ich spočítate, zmodulujte ich \(10^9 + 7\). Potom len spočítajte jednoduchý vzorec, ktorý ste si odvodili, nezabudnite použiť dosť veľké premenné na uloženie čísel a tiež všetky medzivýsledky modulovať \(10^9 + 7\), aby vám tam nič nepretieklo.

Navyše sa vám môže stať, že vo výpočte budete potrebovať deliť dvoma alebo troma. Keďže počítate modulo \(10^9 + 7\), potrebujete namiesto toho násobiť inverznými prvkami týchto čísel. Poradíme vám, že \(500000004 \cdot 2 \equiv 1 \mod 1\,000\,000\,007\) a \(333333336 \cdot 3 \equiv 1 \mod 1\,000\,000\,007\).

Ak vám to nebude fungovať, môžete si naprogramovať aj algoritmus s jedným forcyklom na to, aby ste ľahšie zistili, kde máte chybu.

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ť.