Zadanie

Táto úloha je mierne ťažšou verziou úlohy číslo 1, “Toľko možností”

Po úspechu s pokusmi doma sa rozhodol Luxusko preskúmať, ako sa správa delenie vesmíru na inom mieste. Vycestoval do ďalekých Spojených štátov amerických a pokus zopakoval. V USA však majú mince s inými hodnotami, namiesto 20 centoviek musel použiť 25 centovky.

Úloha

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

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 25 modulo \(10^9+7\).

Príklady

Input:

14

Output:

4

Input:

30

Output:

18

Input:

7

Output:

2

Úloha sa rieši veľmi podobne, ako predošlá úloha Toľko možností, preto sa najprv uistite, že rozumiete riešeniu tej úlohy.

V predošlej úlohe sme využili, že hodnota každej mince je deliteľná všetkými hodnotami menších mincí. Napríklad každé použitie 20-centovej mince nám akoby ubralo možnosť použiť dve 10-centové mince alebo 4 päťcentové alebo 20 1-centových. V tejto úlohe však máme 25-centovú mincu, ktorá nie je deliteľná 10-centovou.

Dajú sa vymyslieť komplikované finty, ako sa s tým vysporiadať ale lepšia cesta je využiť nasledujúci trik. Buď pri platení použijeme párny počet alebo nepárny počet 25-centových mincí. Tým pádom si môžeme preformulovať zadanie tak, že pri platení môžeme používať nové 50-centové mince a najviac jednu 25-centovú.

Vlastne len sčítame počet možností ako zaplatiť sumu \(n\) pomocou mincí \(1,5,10,50\) a sumu \(n-25\) pomocou rovnakej sady mincí. Tieto podúlohy vyriešime veľmi podobne ako predošlú úlohu.

Nasledujúci program obsahuje kostru riešenia s chýbajúcim vzorcom. Je na vás, aby ste daný vzorec doplnili.

#include <iostream>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define idva 500000004LL
#define itri 333333336LL

inline ll mod(ll x) { return x%MOD; }

ll solve(ll n) {
    ll n5 = mod(n/5);
    ll n10 = mod(n/10);
    ll n50 = mod(n/50);
        
    // Tuto spočítame výsledok, ale sami musíte vymyslieť, ako.
    ll vysledok = 0;
    
    return mod(mod(vysledok) + MOD);
}

int main() {
    ll n;
    cin >> n;
    cout << mod(solve(n) + (n>=25)*solve(n-25)) << endl;
}

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