3. O Žabovej krutovláde vzorové riešenie

123

164

001

3

4369383968

353343059

447723168365033648256648424988

42233771

Na začiatok chceme upozorniť, že v tomto vzoráku indexujeme reťazce od nuly, teda reťazec dĺžky \(n\) začína indexom \(0\) a končí indexom \(n-1\).

Počítanie s veľkých číslami

V tejto úlohe budeme často počítať s veľmi veľkými číslami (najväčšie z nich budú rádovo miliónciferné). Počítanie s veľkými číslami je problematické: v mnohých programovacích jazykoch (Java, Pascal, C++) sa nám takéto veľké čísla nezmestia do premennej a aj v jazykoch s neobmedzene veľkými celočíselnými premennými (Python) je výpočet s takýmito veľkými číslami pomalý.

Konečný výsledok (súčet všetkých podreťazcov) však nepotrebujeme vypočítať presne – stačí nám vypočítať jeho zvyšok po delení \(10^9 + 7\). Ak pre nejaké celé čísla \(a, b\) a kladné celé číslo \(m\) chceme vypočítať hodnotu \[(a+b) \bmod m\text{,}\] nič sa s výsledkom nestane, ak \(a\) a \(b\) dopredu vymodulujeme \(m\). Formálne povedané, platí: \[(a+b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m\text{.}\] Podobné tvrdenie platí aj s násobením namiesto sčítania: \[(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m\text{.}\]

Keďže sa všetky naše výpočty budú skladať iba zo sčítaní a násobení, môžeme aj každý medzivýsledok našich výpočtov modulovať číslom \(10^9 + 7\). To nám zaručí, že nebudeme musieť narábať s veľkými číslami, nakoľko budú medzivýsledky zaručene menšie ako \(m\).

Hrubá sila

Najjednoduchšie riešenie je postupne prejsť všetky súvislé podreťazce, premeniť si každý z nich zo stringu na celé číslo a to pripočítať k celkovému výsledku.

Pri premene podreťazca na celé číslo môžeme použiť nasledujúci postup. Na začiatku premeníme prvú (najľavejšiu) cifru podreťazca na celé číslo, ktoré si uložíme do premennej. Potom pokračujeme v čítamí nášho podreťazca zľava doprava a pri každej ďalšej cifre najprv prenasobíme našu premennú desiatimi, potom k nej pripočitáme túto cifru podreťazca a nakoniec premennú zmodulujeme \(10^9 + 7\).

Každý súvislý podreťazec je jednoznačne určený svojím začiatkom a svojím koncom. Prejdeme teda všetky možné začiatky (v poradí zľava doprava) a pre každý začiatok prejdeme všetky možné konce (tiež v poradí zľava doprava). Dokopy teda musíme spracovať \(O(n^2)\) podreťazcov (kde \(n\) je dĺžka vstupného reťazca). Pri spracovávaní jedného podreťazca spravíme \(O(n)\) operácii, keďže začíname jednociferným číslom a postupne to navyšujeme až na potenciálne \(n\)-ciferné číslo. Výsledná časová zložitosť je preto \(O(n^3)\). Čo sa týka pamäťovej zložitosti, tak tá je \(O(n)\). Máme totiž len jeden reťazec dĺžky \(n\) a nejaké pomocné premenné, ktorých je konštantný počet.

#include <iostream>
using namespace std;

#define MOD 1000000007

int main() {
  string str;
  cin >> str;
  int n = str.size();
  
  long long res = 0;
  for (int l = 0; l < n; l++) {
    for (int r = l; r < n; r++) {
      long long sub = 0;
      for (int i = l; i <= r; i++) {
        sub *= 10;
        sub += str[i] - '0';
        sub %= MOD;
      }
      res += sub;
      res %= MOD;
    }
  }
  cout << res << "\n";
  
  return 0;
}

Trochu porozmýšľajme

Ak trocha porozmýšľame, tak zistíme, že sme veľa vecí počítali zbytočne. Napríklad, ak máme reťazec 12345, tak sme začali podreťazcami 1, 12, 123 atď. Hodnotu každého podreťazca (modulo \(10^9+7\)) sme počítali odznovu, čo je zbytočné. Ak sme už vypočítali hodnotu podreťazca 123 a chceme k celkovému výsledku pripočítať podreťazec 1234, nebudeme to počítať znova od jednotky, ale vynásobíme predchádzajúce číslo \(10\), pripočítame \(4\) a zmodulujeme \(10^9 + 7\).

Týmto sa nám časová zložitosť zníži na \(O(n^2)\), keďže zbytočne nepočítame každé číslo odznova. A pre každý začiatok spracujeme všetky konce v čase \(O(n)\). Pamäťová zložitosť ostáva \(O(n)\).

#include <iostream>
using namespace std;

#define MOD 1000000007

int main() {
  string str;
  cin >> str;
  int n = str.size();
  
  long long res = 0;
  for (int l = 0; l < n; l++) {
    long long sub = 0;
    for (int r = l; r < n; r++) {
      sub *= 10;
      sub += str[r] - '0';
      sub %= MOD;
      res += sub;
      res %= MOD;
    }
  }
  cout << res << "\n";
  
  return 0;
}

Ide to aj lepšie

Vzorové riešenie už vyžaduje trošku iný pohľad na vec. Nebudeme sa snažiť čo najoptimálnejšie prejsť všetky súvislé podreťazce, ale zistíme, akou hodnotou daná cifra na indexe \(i\) v reťazci prispieva do konečného výsledku, a tú započítame.

Pozrime sa na príklad, kedy nejaká cifra na \(i\)-tej pozícií má pre rôzne súvislé podreťazce, v ktorých sa nachádza, rôzne hodnoty. Napríklad pre reťazec 1532 má cifra 5 v podreťazci 532 hodnotu \(500\), v podreťazci 53 hodnotu \(50\) atď.

Všimnime si, že prvá cifra v prípade reťazca 1532 je 1 a môže mať najvyššiu hodnotu \(1000\). A čím prechádzame na cifry viac vpravo, tým sa nám najvyššia hodnota zmenšuje. Pre cifru 5 máme maximum \(500\), pre cifru 3 máme maximum \(30\) atď. Taktiež si ale musíme všimnúť, že keď prechádzame na cifry viac vpravo, tak sa nám aj zvyšuje výskyt každej hodnoty o \(1\). Vo vyššie uvedenom príklade pre cifru 1 máme hodnoty \(1\), \(10\), \(100\), \(1000\), všetky iba raz. Pre cifru 5 máme už len hodnoty \(500\), \(50\) a \(5\), ale každú dvakrát, lebo hodnotu \(500\) máme v podreťazcoch 1532 a 532, hodnotu \(50\) v podreťazcoch 153 a 53, hodnotu \(5\) v podreťazcoch 15 a 5. Teraz vieme, že čím ideme viac vpravo tak sa nám maximum najväčšieho možného čísla zmenšuje, ale počet výskytov sa zväčší o 1 pre každú hodnotu.

Takže pre cifru \(c\) na pozícii \(i\) vypočítame jej prispenie do celkového výsledku ako \[(i+1) \cdot \underbrace{111 \ldots 11}_{n-i} \cdot c.\]

Pri výpočte sa nám tým pádom zíde pole veľkosti \(n\), kde na \(i\)-tom indexe bude číslo tvorené \((i+1)\) jednotkami. To číslo ale musíme tiež zmodulovať \(10^9 + 7\), keďže najvyššie možné môže byť až \(n\)-ciferné. Pole vytvoríme jednoducho tak, že definujeme prvý prvok (na indexe \(0\)) ako \(1\) a ďalšie už počítame ako \[(10 \cdot \text{predchádzajúci prvok} + 1) \bmod {10^9 + 7}.\]

Zhrnieme si, čo presne robíme. Najprv si vytvoríme pole dĺžky \(n\), kde na \(i\)-tom indexe poľa máme číslo tvorené \((i+1)\) jednotkami. Potom prechádzame cyklom celý reťazec a pre každú cifru s pomocou tohto poľa vypočítame jej prispenie do celkového výsledku ako \[(i+1) \cdot \underbrace{111 \ldots 11}_{n-i} \cdot c.\]

Medzivýsledky, samozrejme, vždy zmodulujeme \(10^9 + 7\).

Časová zložitosť je v tomto prípade len \(O(n)\), keďže pomocné pole vieme vytvoriť v čase \(O(n)\) a okrem toho stačí len raz prejsť celý reťazec. Pamäťová zložitosť je rovnaká ako pri predchádzajúcich riešeniach, čiže \(O(n)\).

#include <iostream>
#include <string>
using namespace std;
#define modulo 1000000007

int main() {

	long long sum=0;
	string cislo;
	cin >> cislo;
	long long pole[cislo.length()];
	pole[0]=1;
	for(int i=1;i<cislo.length();i++)
		pole[i] = (10*pole[i-1]+1) % modulo;
	
	for(int i=0;i<cislo.length();i++){
		int cifra = ((int)cislo[i])-48;
		
		sum=(sum+((i+1)*cifra*pole[cislo.length()-1-i])) % modulo;

	}

	cout<<sum % modulo<<endl;
	return 0;
}

Úloha ešte má aj riešenie s pamäťovou zložitosťou \(O(1)\), za ktoré sa udeľoval jeden bonusový bod. Neuvádzame ho tu, ale záujemcov podporujeme v tom, aby sa naň pokúsili prísť :)