8. Ozajstná veda vzorové riešenie

5 2
7 7 3 7 77

7

5 3
3 7 77 7 77

4

34 17
14 14 14 ... 14 14 14

333606206

Skoro riešenie

Najprv si úlohu zjednodušme. Čo by sa stalo, keby sme nemali šťastné čísla? Potom by sme vedeli spočítať, koľkými spôsobmi sa dá vybrať \(k\) čísel zo skupiny \(n\) čísel. Je to takzvané kombinačné číslom \[ {{n} \choose {k}} = \frac{n!}{k!(n-k!)}\]

Čo teraz s tými nešťastnými šťastnými číslami?

Zabudnime na chvíľu na čísla, ktoré nie sú šťastné a zoberme si len tie, ktoré obsahujú štvorky a sedmičky. Nech ich je dokopy \(S\). Koľkými spôsobmi vieme z tejto postupnosti \(S\) čísel vybrať \(k\) prvkovú množinu tak, aby tam nebolo žiadne číslo dvakrát? Odpoveď vieme zistiť dynamickým programovaním.

Usporiadajme si šťastné čísla bez duplikátov do postupnosti \(s_1, s_2, \dots, s_m\). Nech je šťastné číslo \(s_i\) na vstupe \(p_i\)-krát. Do tabuľky s rozmermi \(D[m+1][k+1]\) si na políčku \(D[i][j]\) vyrátame, koľkými spôsobmi vieme vybrať množinu obsahujúcu \(j\) prvkov ak používame len šťastné čísla \(s_1, \dots , s_i\) a každé šťastné číslo sa môže vo vybranej množine objaviť najviac raz. Pri rátaní \(D[i][j]\) máme vždy dve možnosti. Ak sme \(s_i\) nevložili do vybranej množiny, tak máme toľko možností, ako pre \(i-1\) čísel a veľkosť množiny \(j\). Ak sme ale \(s_i\) vložili do množiny, tak sme si mohli vybrať jedno z \(p_i\) čísel, ktoré majú hodnotu \(s_i\) a jednu množinu veľkosti \(j-1\), ktorá sa opäť skladá z prvých \(i-1\) čísel. Toto zapíšeme vzorcom: \[D[i][j] = D[i-1][j] + p_i \cdot D[i-1][j-1]\]

V našom dynamickom programovaní zistíme hodnoty \(m \cdot k\) stavov a každý vypočítame v konštantnom čase, takže časová zložitosť bude \(O(mk)\).

Posledné, čo si musíme uvedomiť, je, že počet rôznych šťastných čísel na vstupe, teda hodnota \(m\), je malý. Zhora ho môžeme odhadnúť číslom \(2^{10}-2\), čo je počet všetkých, najviac 9-ciferných štastných čísel. Takisto, aj keď podľa zadania je \(k\) veľké až \(100\,000\), tak v našom dynamickom programovaní sa nám neoplatí skúšať \(k\) väčšie ako \(m\). Z každého šťastného čísla totiž môžeme zobrať najviac jedno. Časová zložitosť bude teda \(O(m^2)\) a keďže \(m\) je rádovo \(1\,000\), takéto riešenie sa nám v pohode zmestí do časového aj pamäťového limitu.

Stačí už len spojiť tieto dve myšlienky a máme úlohu teoreticky vyriešenú. Pre každé \(l\leq m\) vyrátame, koľkými spôsobmi vieme vybrať postupnosť dlhú \(k-l\) len z nie šťastných čísel (čo je kombinačné číslo) a postupnosť dlhú \(l\) zo šťastných čísel (čo je číslo z našej dynamiky). Tieto dve čísla vynásobíme, výsledok sčítame cez všetky \(l\) a máme riešenie.

Kombinačné čísla v modulárnej aritmetike

Nakoľko sú čísla veľké a stačí nám výsledok modulo \(10^9+7\), potrebujeme (chceme (musíme)) používať modulárnu aritmetiku. Konkrétne vieme, že \((a + b) \bmod P = (a \bmod P) + (b \bmod P)\) a \((a \cdot b) \bmod P = (a \bmod P)\cdot (b \bmod P)\). Problém ale je, že potrebujeme rátať veľké kombinačné čísla, v ktorých sa delí. Teda by sme chceli vedieť, koľko je

\[ \frac{a}{b} \bmod P \]

Na pomoc príde Malá Fermatova veta¹, ktorá hovorí, že ak je \(P\) prvočíslo (čo číslo \(10^9+7\) je) a \(b\) je ľubovoľné číslo, tak \(b^{P-1}=1 \bmod P\). Keď túto rovnicu vynásobíme číslom \(a\) a predelíme \(b\), dostaneme:

\[ \frac{a}{b} \bmod P = a \cdot b^{P-2} \bmod P \]

To znamená, že delenie sme si nahradili násobením, ktoré vieme modulovať priebežne, vďaka vyššie spomenutému vzťahu. Číslo \(b^{P-2} \bmod P\) sa inak nazýva inverzný prvok k číslu \(b\).

Predposledná vec, ktorú potrebujeme na riešenie, je rýchle umocňovanie, aby sme hodnotu \(b^{P-2}\) stihli zrátať. Hlavná myšlienka tohto algoritmu je, že ak chceme vypočítať hodnotu \(x^{2y}\), tak nám stačí vypočítať číslo \(x^{y}\), a to umocniť na druhú. Pokiaľ by sme chceli vypočítať \(x^{2y+1}\), tak opäť vypočítame \(x^{y}\), umocníme na druhú a výsledok ešte raz vynásobíme \(x\). Samozrejme, všetky operácie robíme modulo \(P\).

Túto ideu samozrejme aplikujeme rekurzívne, takže pri počítaní \(x^y\) budeme rátať niečo štýlu \(x^{y/2}\), čím dostaneme algoritmus, ktorý umocňuje s časovou zložitosťou \(O(\log(y))\), keďže zakaždým sa exponent, ktorý potrebujeme vyrátať zmenší na polovicu.

Na rátanie kombinačných čísel si teda dopredu predpočítame všetky faktoriály do poľa \(F[\,]\) a k nim si vypočítame inverzné prvky, ktoré si uložíme do poľa \(FI[\,]\). Následne vieme, že

\[{{n} \choose {k}} = F[n]\cdot FI[k] \cdot FI[n-k]\]

Zložitosť

Úspešným zvládnutím všetkých týchto vecí dostaneme správne a dostatočne rýchle riešenie. Zostáva už len odhadnúť časovú zložitosť. Nech \(m\) je počet rôznych šťastných čísel vo vstupnej postupnosti. Potom dynamické programovanie zaberie čas \(O(m^2)\). Predrátanie si hodnôt \(p_i\), ktoré počas neho potrebujeme nám pri použití štruktúry map zaberie čas \(O(n\log m)\).

Naviac si potrebujeme predrátať všetky faktoriály, čo zaberie čas \(O(n)\). No a pri postupnom skúšaní hodnoty \(l\) potrebujeme pre každú z \(m\) možností vyrátať jedno kombinačné číslo v čase \(O(\log(P))\), čo nám pridá zložitosť \(O(m\log P)\).

Keď to dáme všetko dokopy, dostaneme zložitosť \(O(n\log m + m^2 + m\log P)\). Pamäťová zložitosť bude \(O(n+m^2)\), ale ak by sme si v našej dynamike pamätali len posledné dva riadky, dostali by sme zložitosť \(O(n+m)\).

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define For(Q,W) for(long long Q=0; Q<W; Q++)

typedef long long LLD;

LLD PRIME = 1000000007;
LLD faktorial[1000000];

LLD power(LLD a, LLD b){ // umocnovanie
    if(b == 0ll) return 1ll;
    if(b == 1ll) return a;
    LLD pom = power(a, b/2ll);
    if(b%2ll == 0ll) return (pom * pom) % PRIME;
    else return (((pom * pom) % PRIME) * a) % PRIME;
}

LLD inv(LLD x){ // ratanie inverzneho prvku
    return power(x, PRIME-2ll);
}

LLD choice(LLD a, LLD b){ // ratanie kombinacneho cisla
    return (faktorial[a] * inv((faktorial[b] * faktorial[a-b]) % PRIME)) % PRIME;
}

bool is_lucky(LLD x){ // zistime, ci je cislo stastne
    while(x>0){
        if (x%10 != 4 && x%10 != 7) return false;
        x = x/10;
    }
    return true;
}

LLD min(LLD a, LLD b){ // lebo klasicke C++ nema min na long longoch
    if(a<b) return a;
    else return b;
}

int main(){
    faktorial[0]=1ll;
    For(i, 1000000-1) // predratame si faktorial
        faktorial[i+1] = (faktorial[i]*(i+1)) % PRIME; 
    map<LLD, LLD> mapa;
    LLD n, k;
    cin >> n >> k;
    LLD pole[n];
    For(i, n) cin >> pole[i];

    LLD unlucky =0;
    For(i, n){ // stacia nam pocty jednotlivych stastnych cisel
        if (is_lucky(pole[i])){
            if(mapa.count(pole[i])==0){
                mapa[pole[i]]=1;
            }
            else{
                mapa[pole[i]]+=1;
            }
        }
        else unlucky+=1;
    }

    LLD D[mapa.size()+1];
    For(i, mapa.size()+1) D[i]=0;
    D[0] = 1;
    for (map<LLD, LLD>::iterator it=mapa.begin(); it!=mapa.end(); ++it){ // dynamika
        for(LLD i=mapa.size(); i>0; i--){
            D[i] = (D[i] + D[i-1] * it->second) % PRIME;
        }
    }

    LLD ans = 0;
    For(i, min(k+1,  unlucky+1)){ // spocitame pre jednotlive pocty nie stastnych
        if(k-i <= mapa.size())
            ans += choice(unlucky, i) * D[k-i];
        ans = ans%PRIME;
    }
    cout<<ans<<endl;
    return 0;
}