Zadanie
Jedno z najvýnosnejších čokoládových obchodných partnerstiev je medzi FKS (Francúzski Kuchári Sladkostí) a KMS (Konfederácia Maškrtných Spoločností) – tri čokolády od FKSákov sú medzi KMSákmi veľmi obľúbené. Táto zlatá baňa však neunikla pozornosti KSP (Komora Slovenských Pekárov), a tak sa na poslednom zasadnutí rozhodli, že do budúceho roku vyvinú novú čokoládu, ktorou by mohli FKS konkurovať.
Bolo im však jasné, že na to, aby ich čokoláda zožala úspech, nesmie chutiť príliš podobne ako niektorá čokoláda, ktorú pre KMS dodávajú FKS (vďaka obchodnému partnerstvu majú totiž výhodné ceny). Rozhodli sa teda, že ich nová čokoláda musí mať rovnaký chuťový rozdiel od všetkých troch FKS čokolád.
Každá čokoláda na svete sa dá popísať ingredienciami, ktoré sa použivajú na jej prípravu. Chuť čokolády závisí len na jej ingredienciách – teda rozdiel chutí dvoch čokolád je jednoducho počet ingrediencií, v ktorých sa čokolády líšia.
KSP teraz zaujíma koľko rôznych receptov na čokoládu by malo šancu na úspech.
Úloha
Na svete existuje \(n\) ingrediencií, ktoré sa môžu použiť na prípravu čokolády. Recept na čokoládu je teda reťazec dĺžky \(n\), kde \(i\)-ty znak je 1
alebo 0
, podľa toho, či čokoláda \(i\)-tu ingredienciu obsahuje, alebo nie. Pre účely tejto úlohy budeme za recepty na čokoládu považovať všetky takéto reťazce (vrátane reťazca tvoreného samými nulami). Rozdiel chutí dvoch čokolád je počet takých ingrediencií, že jedna z čokolád ju obsahuje, ale druhá nie.
Zistite, koľko rôznych receptov na čokoládu má rovnaký rozdiel chutí od všetkých troch FKS čokolád.
Formát vstupu
V prvom riadku je celé číslo \(n\) (\(1 \leq n \leq 3\cdot 10^5\)) – počet ingrediencií použiteľných na prípravu čokolády.
Nasledujú tri binárne reťazce dĺžky \(n\), každý na samostatnom riadku – recepty FKS čokolád.
Je osem sád testovacích vstupov. Maximálne hodnoty \(n\) v jednotlivých sadách sú nasledovné:
číslo sady | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) |
---|---|---|---|---|---|---|---|---|
\(n \leq\) | \(15\) | \(30\) | \(60\) | \(1\,000\) | \(5\,000\) | \(100\,000\) | \(200\,000\) | \(300\,000\) |
Navyše, na získanie plného počtu za popis stačí riešenie s časovou zložitosťou \(O(n \log n)\). Za dobrý popis s lepšou zložitosťou je možné získať (najviac dva) bonusové body.
Formát výstupu
Nájdite počet čokolád, ktorých rozdiel chutí je rovnaký od všetkých troch FKS čokolád. Keďže tento počet môže byť veľmi veľký, vypíšte jeho zvyšok po delení veľkým prvočíslom \(p\).
Vo všetkých vstupoch bude platiť, že \(p = 1\,000\,000\,007\), avšak pri odhade časovej zložitosti toto číslo nepovažujte za konštantu. Môžete predpokladať, že \(n\) je rádovo menej ako \(p\), avšak nie príliš menej. Riešenie so zložitošťou \(O(n)\) je teda oveľa lepšie ako riešenie so zložitosťou \(O(p)\). Dokonca aj \(O(n^{10})\) je stále lepšie ako \(O(p)\). Na druhú stranu môžete predpokladať, že \(O(\log p) = O(\log n)\), resp. že rozdiel medzi \(n\) a \(p\) je nanajvýš polynomiálny.1 Pri popise riešenia môžete predpokladať, že \(p\) je prvočíslo.
Príklady
Input:
3
101
110
000
Output:
2
Jednou možnosťou je použiť len prvú ingredienciu. Druhou je použiť práve druhú a tretiu.
Input:
6
111111
000000
101110
Output:
12
\(O(\log(n^{100})) = O(100 \log n)= O(\log n)\)↩
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);
}
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ť.