Zadanie
Paulinka1 mala jedného dňa robiť úlohu z databáz. Ako písala riešenie, uvedomila si, že jedáleň práve zatvorila. Bola nedeľa, takže aj všetky obchody boli zatvorené. Žiaľ, musela pokračovať v písaní o hlade a tak miesto databáz Paulinka premýšľala o koláčoch. A tak to aj skončilo. Jej domáca úloha obsahovala databázy všelijakých koláčov.
Keď prišla z ďalekého západu na prázdniny domov, rozhodla sa, že taká databáza koláčov je výborný nápad. Išla ho teda zrealizovať. Po chvíli plánovania prišla na to, že databáza predsalen nie je najlepší spôsob pre uloženie koláčov a namiesto databázy upečie maticu koláčov.
Matica mala \(r\) riadkov a \(s\) stĺpcov a Paulinka upiekla \(n + m\) koláčov. Najskôr prvých \(n\) položila tak, že \(i\)-ty bol v \((i \mod r)\)-tom riadku a \((i \mod s)\)-tom stĺpci.
Následne ešte na niektoré políčka matice položila zvyšných \(m\) koláčov tak, ako sa jej to páčilo. Paulinka mohla položiť aj viacero koláčov do jedného políčka.
Ako finalizovala svoju maticu, rozhodla sa, že niektoré koláče ozdobí maslovým krémom. Samozrejme, nie len tak ledabolo! Každý riadok a každý stĺpec musí obsahovať nepárny počet ozdobených koláčov. Samozrejme, žiadne rearanžovanie koláčov!
Paulinka s krémom stojí nad maticou a premýšľa, ako to urobiť. Ide to vôbec? Koľkými spôsobmi?
Úloha
Koľkými spôsobmi ide ozdobiť koláče v horeuvedenom rozložení tak, aby v každom riadku a stĺpci matice bol nepárny počet ozdobených koláčov?
Dva spôsoby sú rôzne, ak je nejaký koláč ozdobený v jednom a neozdobený v druhom. V jednom políčku môže byť aj viac koláčov.
Formát vstupu
Na prvom riadku dostanete rozmery mriežky \(r, s \leq 10^{9}\) a čísla \(r + s \leq n \leq 10^{9}\) a \(m \leq 10^{5}\) oddelené medzerou.
Na ďalšom riadku je \(m\) čísel, \(r_0\) až \(r_{r-1}\), kde \(r_i\) je riadok \(n + i\)-teho koláča.
Na treťom riadku je \(m\) čísel, \(s_0\) až \(s_{s-1}\), kde \(s_i\) je stĺpec \(n + i\)-teho koláča.
Riadky a stĺpce číslujeme od nuly.
V jednotlivých sadách vstupov platia pre \(r\), \(s\), \(n\) a \(m\) nasledovné obmedzenia:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| \(r, s \leq 10\) | \(r \leq 10\) | \(r, s \leq 10^6\) | \(r, s \leq 10^6\) | \(r, s \leq 10^6\) | \(\gcd(r, s)\leq 10^6\) | \(r, s \leq 10^9\) | \(r, s \leq 10^9\) |
| \(n + m \leq 20\) | \(s < 10^3\) | \(n \leq 5(r + s)\) | \(n = r\cdot s\) | \(n \leq 5(r + s)\) | \(n \leq 10^9\) | \(n \leq 10^9\) | \(n \leq 10^9\) |
| \(n \leq 2^{16}\) | \(m \leq 10^5\) | \(m = 0\) | \(m \leq 10^5\) | \(m \leq 10^5\) | \(m \leq 10^5\) | \(m \leq 10^5\) | |
| \(m \leq 10^5\) |
Navyše, v tretej a siedmej sade stačí vypísať, či existuje aspoň jedno riešenie. Presnejšie, ak je odpoveď nula, tak program má vypísať nulu, a inak môže vypísať akékoľvek kladné číslo.
Formát výstupu
Vypíšte jedno číslo – počet rôznych spôsobov ozdobení koláčov. Keďže toto číslo môže byť veľmi veľké, vypíšte ho modulo \(1\,000\,000\,009\).
Príklad
Input:
2 4 6 2
1 1
3 0Output:
8Jeden možný spôsob ozdobenia koláčov:
Input:
6 4 50 5
0 1 2 3 4
3 3 3 3 3Output:
743544352Tu je možností veľa.
Input:
2 4 6 2
1 0
3 2Output:
0s krátkym i↩
Prvé pozorovanie, ktoré môže skúseným riešiteľom napadnúť je, že pri riešení úloh, ktoré sa odohrávajú v tabuľke si vieme situáciu zakresliť ako bipartitný graf. V jednej časti (partícii) vrcholy reprezentujú riadky a v druhej časti vrcholy reprezentujú jednotlivé stĺpce. Hrany medzi nimi reprezentujú políčka tabuľky. Týmto spôsobom si môžeme úlohu pretransformovať na nasledovnú: Máme bipartitný graf v ktorom môže byť medzi niektorými dvojicami vrcholov viac hrán (počet hrán reprezentuje počet koláčov v danom políčku). Koľkými spôsobom vieme vybrať hrany (ozdobiť koláče/vyfarbiť hrany) tak aby podgraf tvorený všetkými vrcholmi a vybranými (vyfarbenými) hranami spĺňal podmienku, že každý vrchol má nepárny stupeň?
Ďalšie pozorovanie je, že v rôznych komponentoch môžeme hrany vyfarbovať nezávisle od seba. To znamená, že celkový počet možností akým vyfarbíme hrany je súčinom počtu možností ako vyfarbiť hrany v jednotlivých komponentoch.
Poďme si na chvíľu predstaviť, že nejaký z komponentov je strom. To znamená že neobsahuje cykly. Kedy ho vieme vyfarbiť a ako? Ak je vrchol list tak potrebuje aby z neho išiel nepárny počet vyfarbených hrán. Keďže list má iba jednu hranu tak táto hrana musí byť určite vyfarbená. A toto nám teda jednoznačne určuje, že všetky hrany k listom budú vyfarbené. Čo teda ostatné hrany? Uvažujme nasledovný rekurzívny algoritmus na vyfarbenie hrán v strome: Zoberme si vrchol rekurzívne ofarbime všetky hrany v jeho podstorme. Ak sme vyfarbili párny počet hrán vedúcich z vrcholu musíme vyfarbiť ešte aj hranu k otcovi, aby sme pre tento vrchol dostali nepárny počet zafarbených hrán. Keď sa lepšie pozriete na tento algoritmus zistíte že vďaka invariantom v rekurzií vždy je jednoznačne určené, ktoré hrany v strome budú zafarbené. Môže sa však stať, že zistíme, že koreň má zafarbený iba párny počet hrán a s tým nevieme nič spraviť. (Nevedie totiž od neho hrana k otcovi.) Vďaka tomuto algoritmu však vieme, že v každom strome vieme zafarbiť hrany najviac jedným povoleným spôsobom a aj to, že môžu existovať stromy v ktorých sa to nedá.
Prichádza čas na otázku, kedy sa strom nedá zafarbiť. Každý vrchol v storme má nejakú hĺbku. Zoberme si vrcholy v párnych hĺbkach. (koreň je BUNV v hĺbke 0). Z týchto vrcholov všetky hrany idú do vrcholov v nepárnych hĺbkach. Počet zafarbených hrán z vrcholov v párnych hĺbkach sa preto musí rovnať počtu zafarbených hrán z vrcholov v nepárnych hĺbkach. To znamená že musia mať aj rovnakú paritu. Keďže z každého vrchola vedie nepárny počet zafarbených hrán, tak parita počtu vrcholov v párnej hĺbke musí byť rovná parite počtu vrcholov v nepárnej hĺbke na to aby strom išiel zafarbiť. Ak sú rôzne tak práve vtedy sa stane ten prípad že po jednoznačnom zafarbení hrán v strome zistíme že z koreňu vychádza párny počet zafarbených hrán. Ak sú však parity rovnaké práve tento prípad nastať nemôže.
Tento princíp vieme využiť aj na nestromové bipartitné grafy. Teda ak máme ľubovolný komponent tak sa bude dať zafarbiť práve vtedy keď má počet vrcholov na jednej jeho strane a na druhej strane rovnakú paritu. Toto sa dá ľahko dokázať. Ak má počet vrcholov na jednotlivých stranách rôznu paritu a z každého vrcholu vychádza nepárny počet zafarbených hrán potom nám nesedí celkový počet zafarbených hrán z týchto strán(partícii) grafu. Zároveň ak má počet vrcholov rovnakú paritu tak si môžeme z komponentu zobrať jeho kostru. Poďla predchádzajúceho odseku vieme, že táto kostra (strom) sa dá zafarbiť jednoznačným spôsobom a preto existuje aspoň jedno zafarbenie tohoto bipartitného grafu, tak aby boli splnené podmienky zo zadania.
Myšlienka s kostrou je kľúčom k najdôležitejšiemu pozorovaniu úlohy. Uvažujme komponent pre ktorý existuje zafarbenie. Vyberme si z neho ľubovolnú kostru. Všetky ostatné hrany môžeme zafarbiť úplne ľubovolne a stále bude existovať zafarbenie kostry, také aby nám sedela parita v každom vrchole. Ako toto dokážeme? Konštrukciou. Nech všetko v komponente okrem kostry je zafarbené ľubovolne. Teraz poďme zafarbiť hrany v kostre. Opätovne postupujme rekurzívnym prehľadávaním do hĺbky. Keď sa dostaneme k nejakému vrcholu tak najprv zistíme, ako majú byť zafarbené hrany v jeho podstrome. Potom zafarbíme poslednú hranu, ktorá sa ho týka (tú ktorá vedie k jeho otcovi) a to iba v prípade, že pred jej zafarbením by mal vrchol párny počet zafarbených hrán. Takto vieme zafarbiť celý strom okrem koreňu jednoznačným spôsobom. To, že bude mať správnu paritu počtu zafarbených hrán ukážeme nasledovne: Vieme, že počet vrcholov v komponente na jednotlivých stranách (partíciach) má rovnakú paritu. Preto je ich súčet párny. Predstavme si, že by zo všetkých vrcholov vychádzal nepárny počet hrán okrem koreňu z ktorého vychádza párny počet hrán. Potom z vrcholov okrem koreňu celkovo vychádza nepárny počet hrán a z koreňa párny. Celkový súčet počtu vychádzajúcich hrán z vrcholov je nepárny. To je ale v spore s tým že každá hrana vychádza dva krát - raz z každého vrcholu. Preto aj z koreňu musí vychádzať nepárny počet zafarbených hrán.
Ako zistíme počet zafarbení nejakého komponentu? Je to 0, keď je počet vrcholov v komponente nepárny. (Ak je párny tak počet vrcholov na jednotlivých stranách má rovnakú paritu). A je to \(2^k\) keď je počet vrcholov v komponente párny, kde \(k\) je počet hrán ktoré nie sú v kostre. Každú z nich totiž vieme zafarbiť jedným z dvoch spôsobov. Aký je teda celkový počet možných zafarbení? Je to súčin počtu zafarbení jednotlivých komponentov. Ak je teda nejaký komponent nezafarbiteľný tak je výsledok nula. Inak je to súčin mocnín dvojky, teda súčet exponentov. Takže by sme mohli povedať, že je to \(2^{n+m-l}\), kde \(n+m\) je počet hrán a \(l\) je počet hrán v kostrách jednotlivých komponentov. Všimnime si, že tento počet hrán môžeme zase vypočítať nasledovne. Nech \(u\) je počet komponentov. Ak si spojíme kostry, pričom použijeme \(u-1\) hrán, tak dostaneme jednu megakostru ktorá bude mať o jednu hranu menej ako je počet vrcholov. 1 Preto je teda celkový počet zafarbení \(2^{n+m-((r+s-1)-(u - 1))} = 2^{n+m+u-r-s}\). Vypočítať zvyšok tohoto čísla po delení iným (malým číslom) vieme jednoducho cez známy algoritmus v logaritmickom čase od veľkosti tohoto čísla.
Zostala posledná časť úlohy: Zistiť počet komponentov. O čo by to bolo jednoduchšie keby nám v zadaní nenadiktovali dodatočné hrany…
Zoberme si teda ľubovoľný takýto graf. Bez ujmy na všeobecnosti nech \(r>s\). Potom doňho pridáme aspoň \(n>=r+s\) hrán. Pozrime sa na tieto hrany podrobnejšie. Prvých \(r\) hrán nám spojí každý riadok so stĺpcom, ktorý ma číslo rovnaké, ako číslo riadku modulo počet stĺpcov. Týmto nám v grafe zostane už iba \(s\) komponentov. Teraz pridáme ešte \(s\) hrán. Každá spoji riadok s číslom \(i\) (ktorý je už spojený so stĺpcom číslo i) s riadkom s číslom \(i+r \pmod r\). Nech sú všetky komponenty definované číslom stĺpca ktorý sa v nich nachádza po prvých \(r\) hranách. Potom týchto \(s\) ďaľších hrán nám spojí pre všetky \(i\) stĺpec \(i\) so stĺpcom \(i+r \pmod s\). Poďme sa pozrieť na situáciu po pridaní \(r+s\) hrán.
Máme \(s\) stĺpcov (riadky už môžeme ignorovať lebo ku každému máme už jednoznačne priradený stĺpec, ktorý ho zastupuje. (Riadok \(i\) zastupuje stlpec \((i \pmod s)\). Vieme nasledovné: Stĺpec \(i\) je spojený so stĺpcom \(i+r \pmod s\), žiadne ďalšie dodatočné hrany momentálne nemáme. Teda predstavme si to ako situáciu, kde mame nasledovný graf: Každý stĺpec predstavuje jeden vrchol. Stĺpec \(i\) je spojený so stĺpcom \(i+r \pmod s\) a so stĺpcom \(i-r \mod s\).
Tvrdím nasledovné: Stĺpec \(a\) je v jednom komponente so stĺpcom \(b\) práve vtedy, keď \(\gcd(r,s)\) 2 delí \(a-b\).
Dôkaz: Ak existuje cesta z \(a\) do \(b\) tak prechádza nejakými vrcholmi. Všimnime si, že dvojice susediacich vrcholov majú rovnaký zvyšok po delení \(\gcd(r,s)\). Preto počas celej cesty prechádzame vrcholmi s rovnakým zvyškom po delení \(\gcd(r,s)\). Ak teda existuje cesta z \(a\) do \(b\) tak vtedy musia mať \(a\) aj \(b\) rovnaký zvyšok po delení \(\gcd(r,s)\).
Podobne môžeme dokázať, ze ak \(a-b\) delí \(\gcd(r,s)\) tak existuje cesta z \(a\) do \(b\): Z \(a\) sa vieme dostať na najviac \(\frac{s}{\gcd(r,s)}\) vrcholov vrátane \(a\). To je preto, že toľko vrcholov má rovnaký zvyšok po delení \(\gcd(r,s)\) ako \(a\). Vieme sa odtiaľ dostať napríklad na vrcholy \((a \mod s)\), \((a + r \mod s)\), \((a+2r \mod s)\), \((a+3r \mod s)\)… Všimnite si, ze napriek tomu že táto postupnosť je nekonečne dlhá, môže obsahovať len konečne veľa čísel. Preto sa niekedy stane že bude obsahovať dva krát to isté číslo a teda sa nutne niekde zacyklí. Zoberme si teda jej najkratší cyklus a zistime aký je dlhý. Pre nejaké \(k\) a \(j\) nutne platí že \(a+kr \equiv a+jr \pmod s\). Potom ale \((k-j) r \equiv 0 \pmod s\). Počet riadkov \(r\) si vieme rozpísať ako súčin \(r=x \cdot \gcd(r,s)\), kde \(x\) je nesúdeliteľné s \(s\). Potom dostaneme \((k-j)r \equiv (k-j) \cdot x \gcd(r,s) \equiv 0 \pmod s\). Keďže x je nesúdeliteľné nijako nám neovplyvňuje deliteľnosť \(s\). Preto \((k-j) \gcd(r,s) \equiv 0 \pmod s\), no nato aby bolo nejaké číslo deliteľné \(s\) tak musí byť buď 0 alebo aspoň s. Preto \((k-j)\gcd(r,s) \ge s\), teda \(k-j >= s/\gcd(r,s)\) a tým pádom má najkratší cyklus dĺžku aspoň \(s/\gcd(r,s)\). No lenže všimnite si, že už vieme, že v komponente s \(a\) bude najviac \(s/\gcd(r,s)\) vrcholov. Preto v komponente s \(a\) musia byť práve tie vrcholy ktoré majú rovnaký zvyšok po delení \(s/\gcd(r,s)\).
Pozrime sa ešte na to, čo sa stane ak je \(n>r+s\). Všimnite si, že sa vzniknú hrany medzi \((i \pmod r \pmod s)\) a \(i \pmod s\). Tieto čísla však zaručene majú rovnaký zvyšok po delení \(\gcd(r,s)\). Preto sa tým už žiadne ďalšie komponenty nespoja.
Tým pádom po pridaní \(n\) hrán, budú dva stĺpce v jednom komponente práve vtedy keď \(\gcd(r,s)\) delí ich vzdialenosť.
Všimnite si že takto dostaneme \(gcd(r,s)\) komponentov a každý z nich je rovnako veľký, takže si ľahko spočítame ich veľkosť a z toho paritu.
Teraz už zostáva len posledná otázka – ako si zistiť koľko komponentov vlastne máme, keď ich dodatočne pospájame \(m\) hranami. Na tento účel vieme použiť Union-Find, no nebude úplne jednoduché keďže si možno nebudeme vedieť zapamätať všetky vrcholy. Preto spravíme pár drobných zmien. V prvom rade si budeme hlavné vrcholy každého komponentu pamätať v mape namiesto poľa. (Tým pádom si nemusíme pamätať všetky vrcholy, stačia iba tie kde nastala zmena.) Taktiež si budeme pamätať celkový počet komponentov a počet komponentov s nepárnym počtom vrcholov. Okrem toho si zapamätáme o každom komponente či ma párny alebo nepárny počet hrán. Pomocou Union Findu budeme vždy vedieť ľahko zistiť, či hrana spája dva komponenty, ktoré ešte spojené neboli a ak áno, tak budeme vedieť, určiť ktoré to sú. Tým pádom budeme vedieť aktualizovať paritu počtu ich vrcholov a tiež počet komponentov s nepárnym počtov vrcholov. Tým pádom nakoniec budeme vedieť či je komponent s nepárnym počtom vrcholov a koľko komponentov je celkovo v grafe, z čoho budeme vedieť vyrátať odpoveď.
Union find bude potrebovať \(O(m log (r+s))\) krokov vzhľadom k tomu že bude uložený v mape. Umocňovanie spravíme na rádovo \(\log (n+m)\) krokov. Najväčší spoločný deliteľ vieme pomocou Euklidovho algoritmu zrátať radovo v čase \(O(\log (r+s))\). Celková časová zložitosť je teda \(O(m log ^2 (r+s) + log(n+m))\).
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define MOD 1000000009
int exp2 (int e) {
/** 2 to the power of <e>, modulo MOD. */
if (e == 0) {
return 1;
}
long long sub = exp2(e/2);
int res = ((sub*sub) * (e%2 ? 2ll : 1ll)) % MOD;
return res;
}
int gcd (int a, int b) {
/** Greatest common divisor of <a> and <b>. */
if (a < b) {
swap(a, b);
}
while (b != 0) {
a %= b;
swap(a, b);
}
return a;
}
struct DFU {
/** Disjoint find union structure for arbitrarily large graphs. */
map<int, int> parent, rank;
map<int, bool> parity;
int root_of (int v) {
/** Returns the ultimate ancestor of <v>. Also compresses the path
* from <v> to that ancestor. */
if (parent.count(v) == 0) {
return v;
}
int par = parent[v];
int res = root_of(par);
parent[v] = res;
return res;
}
bool same_root (int u, int v) {
/** Returns true if <u> and <v> are in the same component, false
* otherwise. */
return root_of(u) == root_of(v);
}
bool parity_of (int v) {
/** Returns the parity of <u> (the parity of the size of the component
* of <u>). */
v = root_of(v);
if (parity.count(v)) {
return parity[v];
}
return 1;
}
int rank_of (int v) {
/** Returns the rank of vertex <v>. */
if (rank.count(v) == 0) {
return 0;
}
return rank[v];
}
void inc_rank (int v) {
/** Increments rank of <v> by 1. */
if (rank.count(v) == 0) {
rank[v] = 0;
}
rank[v] += 1;
}
void join (int u, int v) {
/** Joins two vertices <u> and <v>. */
u = root_of(u);
v = root_of(v);
if (rank_of(u) == rank_of(v)) {
inc_rank(v);
}
else
if (rank_of(u) > rank_of(v)) {
swap(u, v);
}
int temp = (parity_of(u) + parity_of(v)) % 2; // for WTF_C++?? reasons, one cannot put the right hand size immediately into the line below, but must use this temp variable...
parity[v] = temp;
parent[u] = v;
}
};
struct Grid {
int r, s;
// stuff related to the dimensionality of the vector space
int dim, dim2;
int num_comps, num_taken;
DFU comps;
void load () {
/** Loads all input data: grid dimensions, number of default cakes
* and number of additional cakes. Then loads all the bonus cakes. */
int n, m;
cin >> r >> s >> n >> m;
bool flipped = (r < s);
if (flipped) {
swap(r, s);
}
num_comps = gcd(r, s);
num_taken = s - num_comps;
dim = r + num_taken;
dim2 = n - dim;
// load all the bonus cakes
vector<int> rows(m), cols(m);
for (int i = 0; i < m; i++) {
cin >> rows[i];
}
for (int i = 0; i < m; i++) {
cin >> cols[i];
}
if (flipped) {
swap(rows, cols);
}
// process them
for (int i = 0; i < m; i++) {
int ri = rows[i];
int si = cols[i];
int c_ri = ri % num_comps;
int c_si = si % num_comps;
if (comps.same_root(c_ri, c_si)) {
dim2 += 1;
}
else {
dim += 1;
comps.join(c_ri, c_si);
}
}
}
bool can_generate_ones () {
/** Returns true if we can generate the configuration with all rows
* and columns containing odd number of decorated cakes, false otherwise. */
if (r%2 != s%2) {
return false;
}
if (dim == r+s-1) {
return true;
}
int comp_size = (r+s) / num_comps;
if (comp_size % 2 == 0) {
return true;
}
for (int i = 0; i < num_comps; i++) {
if (comps.parity_of(i)) {
return false;
}
}
return true;
}
void solve () {
if (can_generate_ones()) {
cout << exp2(dim2) << "\n";
return;
}
cout << "0\n";
}
};
int main () {
Grid G;
G.load();
G.solve();
return 0;
}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ť.