7. Dobrý recept vzorové riešenie

3
101
110
000

2

6
111111
000000
101110

12

Stará dobrá hrubá sila

Ako inak – úloha sa dá riešiť aj hrubou silou. Chceme vedieť koľko receptov čokolád má rovnaký rozdiel chutí od tých troch na vstupe. Keďže každý recept je binárny reťazec dĺžky \(n\), možných receptov je \(2^n\). Pre daný recept vieme v lineárnom čase spočítať chuťový rozdiel od každej čokolády na vstupe a keď nám tento rozdiel vyjde rovnaký pre všetky tri čokolády, pripočítame k odpovedi \(1\).

Ostáva nám už len vygenerovať všetky binárne reťazce dĺžky \(n\) čo najpohodlnejšie – napríklad použiť bitovú reprezentáciu čísel; prejdeme všetky čísla od \(0\) po \(2^n - 1\), pričom recept bude posledných \(n\) bitov tohto čísla.

Stačí si nám pamätať reťazce zo vstupu a pár konštantných premenných, pamäťová zložitosť teda bude \(O(n)\). Ako sme už spomínali, skúšame \(2^n\) receptov a pre každý spočítame jeho rozdiel chutí od troch čokolád v lineárnom čase, teda časová zložitosť je \(O(n2^n)\).

#include <iostream>
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    string cokolady[3];
    for (int i=0; i<3; ++i) cin >> cokolady[i];
    for (int mask = 0; mask < (1<<n); ++mask) {
        int rozdiel[3] = {0,0,0};
        for (int i=0;i<3;++i)
            for (int k=0;k<n;++k) 
                if (cokolady[i][k]-'0' != ((mask>>k)&1)) 
                    ++rozdiel[i];
        if (rozdiel[0]==rozdiel[1] && rozdiel[1]==rozdiel[2]) 
            ++ans;
    }
    cout << ans % 1000000007 << "\n";
}

Dynamické programovanie

Úlohu si môžeme zovšeobecniť. Namiesto toho, aby sme hľadali počet receptov, ktoré sa od každej čokolády líšia rovnako, pre každú trojicu \(a,b,c\) spočítame koľko receptov sa líši od prvej čokolády na \(a\) pozíciách, od druhej na \(b\) pozíciách a od tretej na \(c\) pozíciách. Navyše tieto hodnoty postupne spočítame pre \(n\) prípadov: čo keby sme uvažovali len recepty dĺžky \(i\) a porovnávali ich len s prvými \(i\) ingredienciami? Počet reťazcov dĺžky \(i\), ktoré sa od reťazcov na vstupe líšia postupne na \(a\),\(b\),\(c\) z prvých \(i\) pozícií, označíme \(P[i,a,b,c]\).

Vyzerá to, že sme si veľmi nepomohli, lebo teraz musíme spočítať \(O(n^4)\) hodnôt namiesto jednej. No opak je pravdou, pretože tieto hodnoty ľahko spočítame pomocou techniky dynamického programovania.

Pre \(i = 0\) máme len jednu možnosť, ako môže reťazec vyzerať, a tento reťazec sa na žiadnej z \(0\) pozícií od žiadnej z troch čokolád chuťovo nelíši. Takže \(P[0,0,0,0] = 1\) a \(P[0,a,b,c] = 0\) pre ostatné hodnoty \(a,b,c\).

Teraz si ukážeme, ako spočítať \(P[i,a,b,c]\) pre \(i>0\), ak už poznáme hodnoty \(P[\,]\) pre \(i-1\). Pozrime sa na \(i\) tu ingredicenciu. Nech \(a_i,b_i,c_i\) sú postupne \(i\)-te znaky (0 alebo 1) reťazcov na vstupe. Keď zoberieme ľubovoľný reťazec dĺžky \(i-1\), ktorý sa od vstupných troch reťazcov odlišuje postupne na \(a, b, c\) pozíciách, a pridáme na koniec nulu, bude sa od reťazcov líšiť na \(a + a_i\), \(b + b_i\) a \(c + c_i\) pozíciách. Keby sme na koniec pridali jednotku, bude sa odlišovať na \(a + (1 - a_i)\), \(b + (1 - b_i)\) a \(c + (1 - c_i)\) pozíciách. Preto

\[P[i,a,b,c] = P[i-1,a-a_i,b-b_i,c-c_i] + P[i-1,a- (1-a_i),b - (1 -b_i),c - (1 -c_i)]\]

Všimnite si, že súčet hodnôt \(P[i,a,b,c]\) pre všetky možné \(a,b,c\) je \(2^i\), čo je práve počet binárnych reťazcov dĺžky \(i\).

Týmto výrazom dokážeme spočítať všetky hodnoty \(P\) a na konci už len sčítame počet spôsobov, ktorými vieme získať recepty dĺžky \(n\) s rozdielmi chutí \(k\) od všetkých troch čokolád pre \(0 \leq k \leq n\). Čiže postupne sčítame \(P[n,k,k,k]\) pre všetky \(k\).

Výpočet každej z \(O(n^4)\) hodnôt nám trvá konštantne dlho, takže časová zložitosť je \(O(n^4)\).

Pamätáme si všetkých \(O(n^4)\) hodnôt, taká je teda pamäťová zložitosť. Ak si všimneme že pre odpovede na dĺžku receptov \(i+1\) nás už zaujímajú len odpovede pre dĺžku \(i\), môžeme si vždy pamätať len odpovede pre poslednú vypočítanú dĺžku a tú, ktorú práve počítame. Tým by sme sa zlepšili na \(O(n^3)\).

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

int main() {
  int n, mod = 1000000007;
  cin >> n;
  string s[3];
  for (int i = 0; i < 3; ++i) cin >> s[i];

  int dp[n + 1][n + 1][n + 1][n + 1];
  memset(dp, 0, sizeof(dp)); //vynulujeme
  dp[0][0][0][0] = 1;

  for (int i = 0; i < n; ++i)
    for (int a = 0; a <= i; ++a)
      for (int b = 0; b <= i; ++b)
        for (int c = 0; c <= i; ++c)
          for (int znak = 0; znak <= 1; ++znak) {
            // nove rozdiely chuti troch cokolad ak doteraz ich rozdiely boli a/b/c
            // a dalsia ingrediencia v cokolade je (znak = 1) alebo nie je (znak = 0)
            int A = a + (s[0][i] - '0' != znak);
            int B = b + (s[1][i] - '0' != znak);
            int C = c + (s[2][i] - '0' != znak);
            dp[i + 1][A][B][C] += dp[i][a][b][c];
            if (dp[i + 1][A][B][C] >= mod) dp[i + 1][A][B][C] -= mod;
          }

  // scitame pocet receptov pre ktore je rozdiel rovnaky pre vsetky cokolady
  int sum = 0;
  for (int k = 0; k <= n; ++k) sum += dp[n][k][k][k];
  cout << sum % mod << "\n";
}

Myšlienka vzorového riešenia

Dôležité je všimnúť si, že na poradí ingrediencií vôbec nezáleží a jediné dôležité sú tieto štyri počty:

• počet ingrediencií, v ktorých sú druhá a tretia čokoláda rovnaké, ale odlišné od prvej
• počet ingrediencií, v ktorých sú prvá a tretia čokoláda rovnaké, ale odlišné od druhej
• počet ingrediencií, v ktorých sú prvá a druhá čokoláda rovnaké, ale odlišné od tretej
• počet ingrediencií, v ktorých sú všetky tri čokolády rovnaké

Tieto typy pozícií si postupne označíme pozície typu A, typu B, typu C a typu D. (Žiadne iné typy ingrediencií nie sú.) Počty týchto pozícií si označíme postupne \(A,B,C,D\). Riešenie úlohy závisí len od týchto štyroch čísel, akonáhle ich poznáme, môžeme samotné recepty čokolád zabudnúť. Taktiež nie je dôležité, v akom poradí boli čokolády na vstupe uvedené, takže si čísla \(A,B,C\) môžeme poprehadzovať, tak aby platilo \(A\leq B\leq C\). Toto preusporiadanie nám zjednoduší riešenie, lebo nebudeme musieť rozoberať veľa prípadov.

Každý možný výsledný recept \(R\) je charakterizovaný štyrmi číslami

• \(a\) je počet pozícií typu A, na ktorých sa \(R\) líši od prvého reťazca
• \(b\) je počet pozícií typu B, na ktorých sa \(R\) líši od druhého reťazca
• \(c\) je počet pozícií typu C, na ktorých sa \(R\) líši od tretieho reťazca
• \(d\) je počet pozícií typu D, na ktorých sa \(R\) líši od všetkých reťazcov

Pozor, \(a,b,c\) v tejto časti znamenajú niečo úplne iné ako \(a,b,c\) v časti o dynamickom programovaní.

Pomocou čísel \(a,b,c,d\) vieme presne vyjadriť, na koľkých miestach sa líši \(R\) od jednotlivých reťazcov. Napríklad od prvého reťazca sa líši na \(a + (B-b) + (C-c) + d\) pozíciách. Aby sa náš recept líšil na rovnako veľa pozíciách aj od druhého reťazca, musí platiť, že toto číslo je rovné \((A-a) + b + (C-c) + d\). Čiže \(b - a = (B-A)/2\). Podobne zistíme, že \(c - a = (C-A)/2\).

To okrem iného znamená, že ak čísla \(A,B,C\) nemajú rovnakú paritu, tak odpoveď na riešenie úlohy je 0. V opačnom prípade vieme, že rozdiel \(b-a\) a \(c-a\) je konštantný, takže hodnoty \(b\) a \(c\) sú určené hodnotou \(a\). Na hodnote \(d\) nezáleží, takže na pozíciách typu \(D\) môže mať náš reťazec hocičo.

Pre spočítanie odpovede nám teda stačí pre každé \(a\), \(0\leq a\leq A\) zistiť, koľko existuje binárnych reťazcov dĺžky \(n\), ktorých počty jednotiek na jednotlivých typoch pozícií sú \(a\) pre typ A, \(a + (B-A)/2\) pre typ B, \(a + (C-A)/2\) pre typ C a hocikoľko pre typ \(D\).

Pre konkrétne \(a\) je tento počet \(2^D\binom{A}{a}\binom{B}{a+(B-A)/2}\binom{C}{a + (C-A)/2}\). Pričom \(\binom{n}{m}\) označuje “koľkými možnosťami vieme vybrať \(m\) prvkov z \(n\) prvkovej množiny”, čoho hodnota je \(\frac{n!}{m!(n-m)!}\).

Celé riešenie úlohy je \[2^D\sum_{a=0}^{A}{\binom{A}{a}\binom{B}{a+(B-A)/2}\binom{C}{a + (C-A)/2}}\text{.}\]

A zostáva nám už len zistiť, ako čo najrýchlejšie spočítať túto sumu. Opäť si všimnite, že odpoveď závisí len od čísel \(A,B,C,D\), ako sme spomínali na začiatku.

Odporúčame dať si na tomto mieste krátku pauzu a napiť sa vody.

Ako krátke intermezzo spomenieme, že spôsobov ako riešiť túto úlohu vzorovo je viacero a väčšina z nich eventuálne skončí tak, že chceme spočítať nejakú sumu, v ktorej nejako vystupujú kombinačné čísla (to sú tie zvieratká typu \(\binom{n}{m}\)). Podľa toho, ako rýchlo dokážeme spočítať túto sumu rozlišujeme tri hlavné riešenia.

Pomalé kombinačné čísla

Najjednoduchší spôsob ako spočítať sumu je, skonštruovať si prvých \(C\) riadkov Pascalovho trojuholníka. V ňom sa nachádzajú všetky kombinačné čísla, ktoré v sume potrebujeme, takže samotnú sumu spočítame v čase \(O(n)\). Spočítanie Pascalovho trojuholníka nám však zaberie čas \(O(n^2)\).

Modulárne umocňovanie

Už sme spomínali, že kombinačné číslo \({n \choose m}\) sa rovná \(\frac{n!}{(n-m)!m!}\). Faktoriály vyriešime ľahko, tie si vieme na začiatku predpočítať v čase \(O(n)\). Problém však robí delenie modulo \(p\). Pre ilustráciu aké ťažké je deliť, môžete skúsiť zhlavy spočítať, koľko je \(7\) deleno \(13\) modulo \(10^9+7\)? (Je to \(76923078\).) Namiesto delenia preto budeme násobiť inverzným prvkom. Náš prípad, pre \(p = 10^9+7\), by vyzeral takto: \(7/13 \equiv 7\cdot 13^{-1} \equiv 7\cdot 13^{p-2} \equiv 7\cdot 153846155 \equiv 76923078 \pmod p\). Pre overenie spočítame, že \(13\cdot 76923078 \equiv 1000000014 \equiv 7 \pmod p\). Viac sa môžete dočítať v článku o modulárnom umocňovaní a inverzných prvkoch.

Pre nás je dôležité, že inverzný prvok vieme spočítať v čase \(O(\log p)\). Inverzný prvok potrebujeme poznať pre každý faktoriál, takže dokopy je to \(O(n\log p)\) času, čo podľa podmienky v zadaní je \(O(n\log n)\).

Vzorové riešenie v \(O(n)\)

Po tom, ako si rozpíšeme kombinačné čísla na faktoriály, dokážeme celú sumu napísať v tvare \(\sum_{a=0}^{A}{\left(\frac{x_a}{y_a}\right)}\). Ak si dopredu predpočítame hodnotu faktoriálov od \(1!\) po \(n!\) modulo \(p\), dokážeme vypočítať každú z hodnôt \(x_a\), \(y_a\) v konštantnom čase.

Teraz si ukážeme všeobecný algoritmus, ktorý dokáže takúto sumu v tvare \(\sum_{i=0}^{n}{\frac{x_i}{y_i}}\) spočítať modulo ľubovoľné prvočíslo v čase \(O(n)\). Tým vlastne dostaneme vzorové riešenie celej úlohy v čase \(O(n)\). Kľúčom k riešeniu je, že chceme počítať inverzný prvok len raz (pretože ak by sme ho počítali \(n\)-krát, trvalo by nám to \(O(n\log n)\) času). Preto si sumu prevedieme na spoločný menovateľ čím dostaneme \[\frac{x_1y_2\cdots y_n + x_2y_1y_3\cdots y_n + \cdots + x_ny_1\cdots y_{n-1}}{y_1\cdots y_n}\]

Už máme síce len jedno delenie, ale potrebujeme spočítať všetky súčiny \(y_1\cdots y_n\) bez jedného prvku. Postavme si teda binárny strom, ktorý bude mať v listoch hodnoty \(y_1\cdots y_n\), pričom postupnosť \(y\) doplníme na konci jednotkami, aby jej dĺžka bola mocnina dvoch. Nájdeme teda také \(k\), že \(n\leq 2^k\). Vrcholy stromu si zhora očíslujeme \(1\) až \(2^{k+1}-1\) (tak, že vrchol \(v\) má synov \(2v\) a \(2v+1\)). Tento strom prejdeme odspodu a pre každý vrchol \(v\) si v konštantnom čase spočítame hodnotu \(Y_v\), súčin \(y\)-ov v listoch jeho podstromu. Na to nám stačí vynásobiť hodnoty \(Y\) v jeho synoch: \(Y_v = Y_{2v} \cdot Y_{2v+1} \mod p\).

Prejdeme binárny strom znova, tentokrát odvrchu a spočítame si hodnoty \(Y'_v\) definované nasledovne:

• \(Y'_1 = 1\),
• \(Y'_{2v} = Y'_v \cdot Y_{2v+1} \mod p\) pre \(1 \leq v \leq 2^k-1\)
• \(Y'_{2v+1} = Y'_v \cdot Y_{2v} \mod p\), pre \(1 \leq v \leq 2^k-1\)

Rozmyslite si, že hodnoty \(Y'_v\) predstavujú súčin všetkých \(y\) okrem tých v listoch podsromu \(v\), takže hodnoty \(Y'\) v listoch stromu sú hľadané súčiny.

Celé to vieme spočítať dvoma prechodmi binárneho stromu v čase \(O(n)\). Pamäťová zložitosť riešenia je tiež \(O(n)\). Lepšiu časovú zložitosť dosiahnuť nevieme, pretože musíme načítať celý vstup.

#include<cstdio>
#include<algorithm>
using namespace std;
#define For(i, n) for(int i = 0; i<int(n); ++i)
typedef long long ll;

inline ll mod(const ll& x) { return x % 1000000007; }
inline ll inv(ll x) {  // Inverzny prvok ku x
    int e = 1000000005;
    ll r = 1;
    while (e > 0) {
        if (e%2) r = mod(r*x);
        x = mod(x*x);
        e/=2;
    }
    return r;
}
char cok[3][300047];  // cokolady
int n;
ll A, B, C, D, pocet = 1;
ll F[300047], Y[400047], YY[400047]; // A<=100000

int main() {
    // spracujeme vstup
    scanf("%d %s %s %s", &n, cok[0], cok[1], cok[2]);
    For(i, n) {
        A += cok[0][i] != cok[1][i] && cok[1][i] == cok[2][i];
        B += cok[0][i] != cok[1][i] && cok[0][i] == cok[2][i];
        C += cok[0][i] == cok[1][i] && cok[0][i] != cok[2][i];
        D += cok[0][i] == cok[1][i] && cok[0][i] == cok[2][i];
    }
    // ked nesedi parita, odpoved je 0
    if ((A+B)%2 || (A+C)%2) {
        printf("0\n");
        return 0;
    }
    // utriedime A,B,C
    if (A > B) swap(A,B);
    if (B > C) swap(B,C);
    if (A > B) swap(A,B);
    ll BA = (B-A)/2, CA = (C-A)/2;
    // spocitame mocninu dvojky, faktorialy, citatele sumy
    For(i, D) pocet = mod(pocet * 2);
    F[0] = 1;
    For(i, C) F[i+1] = mod((i+1)*F[i]);
    pocet = mod(mod(pocet*F[A])*mod(F[B]*F[C]));
    // mocnina dvojky vacsia ako A
    int npow = 8;
    while(npow <= A) npow *= 2;
    // najdeme menovatele sumy
    For(i, npow*2) Y[i] = 1;
    For(i, A+1) {
        Y[npow+i] = mod(
            mod(F[i]*F[A-i]) *
            mod(
                mod(F[BA+i]*F[B-BA-i]) *
                mod(F[CA+i]*F[C-CA-i])
            )
        );
    }
    // spocitame sumu(i=0..A) 1/Y[npow+i] v O(n)
    for(int i = npow-1; i>0; --i) {
        Y[i] = mod(Y[2*i]*Y[2*i+1]);
    }
    YY[1] = 1;
    for(int i = 1; i<npow; ++i) {
        YY[2*i] = mod(YY[i] * Y[2*i+1]);
        YY[2*i+1] = mod(YY[i] * Y[2*i]);
    }
    ll suma = 0, menovatel = 1;
    For(i, A+1) {
        suma += YY[npow+i];
        menovatel = mod(menovatel*Y[npow+i]);
    }
    pocet = mod(mod(pocet*inv(menovatel)) * mod(suma));
    printf("%lld\n", pocet);
}