Zadanie

Kedysi dávno, v časoch, keď vo svete ešte vládla mágia a po vonku si voľne behali zázračné bytosti, v jednej ďalekej krajine s názvom Krataria, žilo \(N\) čarodejov. A ako iste viete, každý poriadny čarodej potrebuje svoju vlastnú vežu, v ktorej bude vykonávať svoje experimenty, vymýšľať nové kúzla, variť lektvary a inak čarovať… Taktiež je celkom logické, že keď budú mať dvaja čarodejovia vežu s rovnakou výškou, nebudú sa mať radi a nedopadne to dobre. Preto sa rozhodli, že spolu budú priateľsky súperiť o to, kto bude mať akú výšku veže. Po dlhoročnom súperení boli nakoniec zoradení a každý z nich vedel, ktorá z veží vysokých od \(1\) po \(N\) mu patrí. Keď si už obyvatelia konečne mysleli, že budú mať pokoj, čarodejovia začali s výstavbou svojich veží a rozruch pokračoval. Každý čarodej si vybral nejaké miesto na hranici Kratarie, kde si svoju vežu postavil. Tieto veže boli však také obrovské a drahé na výstavbu, že sa Krataria ocitla v kríze a ich výstavba trvala dlhé roky. Už to vyzeralo tak, že sa výstavba bude musieť zrušiť, avšak stálo to za to. Krataria sa od momentu dokončenia výstavby stala najmocnejšiou krajinou na celom svete. Nikto sa nikdy neodvážil na ňu zaútočit. Tak to aspoň hovorí legenda o Kratarii.

Existuje ešte jedna legenda, z ktorej sa síce zachovali iba útržky, ale spomína sa v nej \(N\) veží:

V legende sa spomína pustatina, v ktorej žijú draky a celá táto pustatina je obklopená \(N\) vežami. Drakom sa tieto veže nepáčia a preto možno niekoľkokrát zničili niektoré najvyššie poschodia niektorých veží. Tiež sa spomína presný popis toho, ako draky ničia poschodia, ale nie to, či sa to aj naozaj stalo alebo koľkokrát sa to stalo. Draky ničia poschodia tak, že každú vežu znížia na minimum jej výšky a výšky predošlej veže.

Dnes sa nám podarilo odkryť pozostatky poslednej veže. Som presvedčený, že tieto pozostatky patria vežiam z legiend. Teraz už len zostáva zistiť, ako vyzerali veže pôvodne, teda koľko možností spĺňa to, čo sa píše v legendách.

denník archeologickej jednotky 0471

Úloha

Na vstupe dostanete postupnosť \(N\) čísel (\(1 \le P_i \le N\)).

Nájdite počet permutácií čísel \(1\)\(N\), z ktorých je možné dosiahnuť postupnosť \(P\) opakovaním (možno aj 0-krát) nasledovnej operácie:

Pre každé \(1 \le i \le N\), \(b_i = \min(a_{i-1}, a_i)\), pričom \(n = 0\), kde \(a\) je postupnosť pred operáciou a \(b\) postupnosť po operácii.

Na štandardný výstup vypíšte hľadaný počet modulo 1000000007.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(N\) (\(1 \le N \le 1000000\)). Na druhom riadku je výsledná postupnosť čísel \(P\), zapísaná ako \(N\) medzerami oddelených čísel. (\(1 \le P_i \le N\))

Formát výstupu

Vypíšte jedno číslo - počet permutácií, z ktorých vieme dostať postupnosť \(P\) opakovaním vyššie uvedenej operácie. Keďže tento počet môže byť veľmi veľký, vypisujte ho modulo \(10^9+7\).

Príklady

Input:

4
2 1 1 2

Output:

2

Postupnosti \((3, 1, 4, 2)\) a \((4, 1, 3, 2)\) spĺňajú podmienky.

Input:

6
6 3 1 1 2 2

Output:

0

Neexistuje žiadna permutácia, ktorá spĺňa podmienky.

Input:

7
4 3 3 1 1 1 2

Output:

18

Počet operácii

Konštanta \(K\) nech predstavuje počet jednotiek na vstupe. Ak je vstup validný, respektíve ak existuje aspoň jedna permutácia, ktorá sa po konečnom počte operácií zmení na postupnosť na vstupe, tak počet vykonaných operácií je rovno \(K-1\), pretože po každej operácií sa úsek jednotiek zväčši o jedna.

Úseky

Na základe počtu operácií sa pre každé číslo na vstupe dá určiť úsek pozícií, kde sa v pôvodnej permutácií toto číslo mohlo nachádzať. Treba si však všimnúť, že číslo sa nemohlo nachádzať na pozícii, kde do \(K\) pozícií od neho sa na vstupe nachádza väčšie číslo. Na základe tohto sa nemôžu dva úseky prekrývať, pretože by to znamenalo, že na rovnakej pozícii môžu byť dve rôzne čísla, ktoré sa v postupnosti zo vstupu nachádzajú. To by znamenalo, že do \(K\) pozícií od tejto spoločnej sa na vstupe nachádzajú obe čísla, ale pritom platí, že jedno z týchto čísel je menšie a nemôže sa teda na tejto pozícii nachádzať.

        vstup: 1 1 1 2 2 4
        úseky: 1   2 4 4 4
               1 · 1 · 3

Tieto úseky vieme nájsť jedným prechodom vstupu: Ak narazíme na prechod z väčšieho čísla na menšie, znamená to, že úsek väčšieho čísla môže začínať najskôr \(K\) pozícií pred ním a končiť najneskôr na jeho pozícii, a že úsek menšieho čísla môže začínať najskôr a končiť najneskôr na svojej pozícii. A podobne naopak, ak narazíme na prechod z menšieho na väčšie, úsek menšieho môže začínať najskôr a končiť najneskôr \(K\) pozícií pred jeho pozíciou a úsek väčšieho môže začať najskôr \(K\) pozícií pred svojou pozíciou a končiť najneskôr na svojej pozícii.

Dolné hranice

Spomínané úseky však nijako neurčujú kde sa môžu nachádzať zvyšné čísla, ktoré sa na vstupe nevyskytujú. Pre tieto čísla vieme určiť dolné hranice, teda pre každú pozíciu najmenšie číslo ktoré sa tam mohlo nachádzať v pôvodnej permutácií. Teda dolná hranica pre nejakú pozíciu je určená maximom na intervale dĺžky \(K\) začínajúcom na tejto pozícii. Toto sa dá nájsť pomocou okienkového minima.

        vstup: 1 1 1 2 2 4
        úseky: 1   2 4 4 4
dolné hranice: 1 2 2 4 4 4

Všimnime si, že pre každú pozíciu v úseku je rovnaká dolná hranica. Je to tak, pretože dolná hranica nemôže byť menšia ako číslo, ktorého je to úsek, a zároveň na týchto pozíciach môže byť aspoň to číslo. Z tohto dôvodu, keď si zvolíme niektorú možnú pozíciu pre číslo z jeho úseku, dolné hranice sa nezmenia a teda môžme voliť pozície a čísla ktoré sa na vstupe nenachádzajúcu podľa dolných hraníc nezávislo na sebe.

Potrebujeme si však ešte rozmyslieť, ako vyberať čísla, ktoré na vstupe nie sú. Môžu byť kdekoľvek, kde nie je žiaden úsek a ak tam úsek je, tak jednu (ľubovoľnú) pozíciu vynecháme, pričom musia vyhovovať dolným hraniciam. Ak by sme tieto čísla vyberali akokoľvek, mohlo by sa stať, že by pre pozície s vyššou dolnou hranicou nezostalo číslo. Keďže platí, že pre pozíciu s vyššou dolnou hranicou je na výber podmnožina čísel ako pre pozíciu s nižšou, tak môžme vyberať náhodne od pozícií s väčšou. Na to však treba tieto dolné hranice zoradiť podľa veľkosti, pričom si stačí uvedomiť, že na ne vieme použiť counting sort.

        vstup: 1 1 1 2 2 4
        úseky: 1   2 4 4 4
               1 · 1 · 3
dolné hranice: 1 2 2 4 4 4
                 3
 zvyšné čísla:   5   5 5
                 6   6 6

Výsledok je tým pádom \(1 \cdot 1 \cdot 3\) (úseky) krát \(2 \cdot 1 \cdot 1\) (zvyšné čísla), teda dokopy \(3 \cdot 2 = 6\)

Možné postupnosti:

1 3 2 4 5 6
1 3 2 4 6 5
1 3 2 5 4 6
1 3 2 6 4 5
1 3 2 5 6 4
1 3 2 6 5 4

Neplatné vstupy

Na vstupe musí byť aspoň jedna jednotka. Všetky rovnaké čísla na vstupe musia tvoriť jeden súvislý interval. Pri hľadaní úsekov, nemusí existovať neprázdny úsek alebo pri vyberaní zvyšných čísel nemusí byť možné čísla rozdeliť. V týchto prípadoch neexistuje žiadna permutácia ktorá sa po \(K-1\) operáciach zmení na zadanú postupnosť, teda výsledok je \(0\).

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


int main() {
	
	int n; cin >> n;
	deque <int> A(n);
	int k = 0;
	for (int i = 0; i < n; i++) { // O(n)
		cin >> A[i];
		if (A[i] == 1) k++;
	}
	
	if (k == 0) {
		cout << 0 << endl;
		return 0;
	}
	
	if (k == n) { // out = n!
		uint64_t out = 1;
		for (int i = 2; i <= n; i++) out = out * i % pn;
		cout << out << endl;
		return 0;
	}
	
	while (A.front() != 1 || A.front() == A.back()) {
		A.push_front(A.back());
		A.pop_back();
	}
	A.shrink_to_fit();
	
	bool possible = true;
	vector <bool> notInA(n+1, true);
	for (int i = 1; i < n; i++) { // O(n)
		if (A[i-1] != A[i] && !notInA[A[i]]) possible = false;
		notInA[A[i]] = false;
	}
	if (!possible) {
		cout << 0 << endl;
		return 0;
	}
	
	deque <array <int, 3>> u;   // {num, left, right}
	deque <int> mxw;            // max window {pos}
	vector <int> l(n, 1); // lower bounds
	vector <int> lc(n+1);    // lc[i] - count of numbers not in A and at least i
	lc[n] = notInA[n];
	u.push_front({A.back(), n-k, n-1});
	for (int i = n-1; i >= 1; i--) {                                    // O(n)
		while (!mxw.empty() && A[mxw.front()] <= A[i]) mxw.pop_front(); // O(1)
		mxw.push_front(i);
		if (mxw.back() == i+k) mxw.pop_back();
		l[i] = A[mxw.back()];
		
		if (A[i-1] != A[i]) {
			u.front()[2] = min(u.front()[2], i);
			if (A[i-1] < A[i]) {
				u.push_front({A[i-1], i-k, i-k});
			} else if (A[i-1] > A[i]) {
				u.front()[1] = max(u.front()[1], i);
				u.push_front({A[i-1], i-k, i-1});
			}
			if (u.front()[1] > u.front()[2]) {
				cout << 0 << endl;
				return 0;
			}
		}
		
		lc[i] = lc[i+1] + notInA[i];
	}
	
	/*
	for (int i = 0; i < n; i++) cout << A[i] << ' ';
	cout << endl;
	for (int i = 0, j = 0; i < n; i++) {
		if (j < u.size() && i >= u[j][1]) {
			cout << u[j][0] << ' ';
			cout.flush();
		} else {
			cout << "  ";
		}
		if (i == u[j][2]) j++;
	}
	cout << endl;
	for (int i = 0; i < n; i++) cout << l[i] << ' ';
	cout << endl;
	*/
//	for (auto i : u) cout << i[0] << ' ' << i[1] << ' ' << i[2] << endl;
	
	uint64_t out = 1;
	vector <int> countSort(n+1, 0);
	for (int i = 0, j = 0; i < n; i++) {// |u[i]| < 0 - not possible
//		if (i == u[j][2]) out = out * max(0, u[j][2]-u[j][1]+1) % pn, j++;
		if (i == u[j][2]) {
			if (j < (int)u.size()) out = out * max(0, u[j][2]-u[j][1]+1) % pn, j++;
		} else countSort[lc[l[i]]]++;
	}
//	for (int i = 0; i < n+1; i++) cout << i << ' ' << lc[i] << ' ' << countSort[i] << endl;
	for (int i = 0, removed = 0; i < (int)countSort.size() && out; i++) { // O(n - |u|)
		while (countSort[i]) {
			out = out * (i-removed) % pn;
			countSort[i]--, removed++;
		}
	}
	
	cout << out << endl;
	
	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ť.