7. Telefonát vzorové riešenie

4

2

8

23

72

100110164

Na začiatok si uvedomme, že ciferný súčin nám dáva akýsi rozklad čísla \(n\) na súčin, ktorého každý člen tvorí samostatná cifra. To ale znamená, že v prvočíselnom rozklade čísla \(n\) (čo je jemnejší rozklad) sa môžu nachádzať iba prvočísla menšie ako 10. V opačnom prípade číslo s daným ciferným súčinom neexistuje a odpoveď je 0.

Neprvočíselné cifry a ciferný súčet

Medzi ciframi našeho čísla sa môžu nachádzať aj neprvočíselné hodnoty, preto nám rozklad \(n\) na prvočísla nedá jednoznačnú sadu cifier, ktorú musíme použiť. Toto sa týka cifier 4, 6, 8 a 9, v našom riešení sa preto budeme musieť rozhodnúť, koľko prvočísel 2 a 3 použijeme na ich vytváranie. Presnejšie, budeme sa musieť rozhodnúť, koľko cifier 4, 6, 8 a 9 chceme mať vo výslednom čísle.

Zabudnúť nemôžeme ani na druhú podmienku zadania – ciferný súčet, ktorý sa tiež musí rovnať \(n\). Ciferný súčet je však väčšinou oveľa menší ako súčin, číslo preto vieme doplniť potrebným počtom cifier 1, ktoré ciferný súčin nemenia.

Ako vybrať sadu použitých cifier?

Koľko možností máme na výber počtu jednotlivých cifier? Vieme napríklad, že nemôžeme použiť žiadnu cifru 0, pretože celý ciferný súčin by bol tiež 0. A keďže poznáme prvočíselný rozklad \(n\), vieme, že naše číslo musí obsahovať rovnaký počet 5 a 7 ako je v tomto rozklade. Otázne sú iba cifry 4, 6, 8 a 9, keby sme vedeli, koľko ich bude vo výsledku, počet 2 a 3 si vieme dopočítať z celkového počtu týchto čísel v rozklade.

Skúsime teda všetky možnosti, lebo vieme, že maximálny počet jednej cifry môže byť najviac \(\log n\), keďže ich súčin nesmie presiahnuť hodnotu \(n\). Určením týchto cifier sú už všetky ostatné jednoznačne dané, počet 1 dopočítame tak, aby sedel ciferný súčet (ak by nám tento počet vyšiel záporný, tak počty ostatných cifier nevyhovujú žiadnemu číslu).

Koľko možných čisiel máme pre danú sadu cifier?

Keď už vieme koľko jednotlivých cifier chceme použiť v našom čísle, potrebujeme zvoliť ich poradie. To totiž nemení ciferný súčet ani súčin, chceme preto zarátať všetky možné preusporiadania. Toto je už však pomerne ľahká kombinatorická úloha, ak si počet cifry \(i\) označíme ako \(P_i\) a počet všetkých cifier dokopy ako \(x\), počet preusporiadaní je:

\[\binom{x}{P_1} \binom{x-P_1}{P_2} ... \binom{x-P_1- ... - P_8}{P_9} = \frac{x!}{P_1! P_2! ... P_9!}\].

Na daný vzorec sa môžete pozerať cez kombinačné čísla (ľavá strana), keď si postupne volíme na ktoré pozície dáme ktoré cifry a počet voľný pozícií sa zmenšuje, alebo ako na permutácie s opakovaním (pravá strana), kde najskôr započítame všetky možné preusporiadania a potom odstraňujeme (delíme) tie, kde sme iba zmenili poradie rovnakých cifier.

Celkový počet cifier bude kvôli cifernému súčtu určite najviac \(n\) a preto si vieme predpočítať všetky faktoriály až po hodnotu \(x\) dopredu a to dokonca modulo \(10^9+7\). Tu však nastáva problém, pretože v okamihu, keď začneme čísla modulovať, normálne delenie prestane správne fungovať. Našťastie, na vyriešenie tohto problému poznáme pomerne klasickú techniku inverzných prvkov. Pre každý faktoriál si vypočítame aj jeho inverzný prvok a keď týmto faktoriálom potrebujeme deliť, namiesto toho delené číslo vynásobíme inverzným prvkom delenca. Keďže hodnota \(p=10^9+7\), ktorú používame na modulovanie je prvočíslo platí, že inverzný prvok čísla \(a\) je rovný \(a^{p-2}\).

V prípade, že sa chcete o inverzných prvkoch dozvedieť niečo viac, prečo ich potrebujeme a počítame práve daným spôsobom, navštívte našu kuchárku a prečítajte si článok o Počítaní modulo prvočíslo.

Časová a pamäťová zložitosť

Najprv si potrebujeme predpočítať všetky faktoriály a ich inverzy, čo nám zaberie \(O(n \log p)\) času (\(p = 10^9+7\)), keďže na vypočítanie inverzu čísla ho musíme umocniť na \(p-2\), čo vieme spraviť v logaritmickom čase. Následne musíme vygenerovať všetky možné počty cifier 4, 6, 8 a 9, každej z nich môže byť najviac \(O(\log n)\), čo dáva dokopy zložitosť \(O(\log^4 n)\). Počty týchto cifier jednoznačne určujú počty zvyšných cifier, ostáva teda výpočet všetkých preusporiadaní vybranej sady cifier. To vieme spraviť v konštantnom čase, keďže faktoriály a ich inverzy už máme predpočítané. Celková časová zložitosť našeho riešenia je \(O(n \log p)\).

V pamäti musíme mať predrátané všetky faktoriály, teda pamäťová zložitosť bude \(O(n)\)

#include <bits/stdc++.h>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)

typedef long long ll;

int n;
ll res=0, MOD = 1000000007;

vector<int> P;
vector<ll> F, I;

ll umocni(ll a, ll b) {
    ll res1=1;
    while(b>0) {
        if(b%2 == 1) res1=(res1*a)%MOD;
        a=(a*a)%MOD;
        b/=2;
    }
    return res1;
}

void init() {
    F.push_back(1);
    for(int i=1; i<300047; i++) F.push_back((F[i-1]*i)%MOD);
    For(i, F.size()) I.push_back(umocni(F[i],MOD-2));
}

void rek(int maxi) {
    if(maxi <= 4 && P[2] >= 2) {
        P[2]-=2; P[4]++;
        rek(4);
        P[2]+=2; P[4]--;
    }
    if(maxi <= 6 && P[2] >= 1 && P[3] >= 1) {
        P[2]--; P[3]--; P[6]++;
        rek(6);
        P[2]++; P[3]++; P[6]--;
    }
    if(maxi <= 8 && P[2] >= 3) {
        P[2]-=3; P[8]++;
        rek(8);
        P[2]+=3; P[8]--;
    }
    if(maxi <= 9 && P[3] >= 2) {
        P[3]-=2; P[9]++;
        rek(9);
        P[3]+=2; P[9]--;
    }
    P[1]=n;
    for(int i=2; i<=9; i++) P[1]-=i*P[i];
    if(P[1] < 0) return;
    int suc=0;
    For(i,10) suc+=P[i];
    ll pocet = F[suc];
    For(i,10) {
        pocet = (pocet * I[P[i]]) % MOD;
    }
    res = (res+pocet)%MOD;
}

int main() {
    init();
    scanf(" %d",&n);
    P.clear();
    P.resize(10,0);
    int p=n;
    for(int i=2; i<=9; i++) {
        while(p%i == 0) {
            P[i]++;
            p/=i;
        }
    }
    if(p != 1) {
        printf("0\n");
        return 0;
    }
    res=0;
    rek(0);
    printf("%lld\n",res);
}