Оруулах-хасах зарчим¶

Оруулах-хасах зарчим бол олонлогийн хэмжээ буюу нийлмэл үзэгдлийн магадлалыг тооцоолох чухал комбинаторик арга юм. Энэ нь тус тусын олонлогийн хэмжээг тэдгээрийн нэгдэлтэй холбодог.

Батламж¶

Үгэн томьёо¶

Оруулах-хасах зарчмыг дараах байдлаар илэрхийлж болно:

Хэд хэдэн олонлогийн нэгдлийн хэмжээг тооцоолохын тулд эдгээр олонлогийн хэмжээг тус тусад нь нийлбэрлэж, дараа нь олонлогуудын бүх хос хосоор-ын огтлолцлын хэмжээг хасаж, дараа нь олонлогуудын гурвал-ын огтлолцлын хэмжээг эргүүлж нэмж, олонлогуудын дөрвөл-ийн хэмжээг хасах ба ингэсээр бүх олонлогийн огтлолцол хүртэл үргэлжлүүлэх хэрэгтэй.

Олонлогийн хэллэгээр томьёолох¶

Дээрх тодорхойлолтыг математик байдлаар дараах байдлаар илэрхийлж болно:

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n|A_i| - \sum_{1\leq i<j\leq n} |A_i \cap A_j| + \sum _{1\leq i<j<k\leq n}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} | A_1 \cap \cdots \cap A_n |$$

Илүү товч байдлаар:

$$\left|\bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}} (-1)^{|J|-1}{\Biggl |}\bigcap_{j\in J}A_{j}{\Biggr |}$$

Венн диаграм ашиглан томьёолох¶

Диаграм нь $A$, $B$, $C$ гэсэн гурван олонлогийг харуулж байг:

Венн диаграм

Тэгвэл тэдгээрийн нэгдэл $A \cup B \cup C$-ийн талбай нь $A$, $B$, $C$-ийн талбайн нийлбэрээс давхар бүрхэгдсэн $A \cap B$, $A \cap C$, $B \cap C$ талбайг хассан, гэхдээ гурван олонлогоор бүрхэгдсэн $A \cap B \cap C$ талбайг нэмсэнтэй тэнцүү:

$$S(A \cup B \cup C) = S(A) + S(B) + S(C) - S(A \cap B) - S(A \cap C) - S(B \cap C) + S(A \cap B \cap C)$$

Үүнийг мөн $n$ олонлогийн нэгдлийн хувьд ерөнхийлж болно.

Магадлалын онолын хэллэгээр томьёолох¶

Хэрэв $A_i$ $(i = 1,2...n)$ нь үзэгдлүүд, ${\cal P}(A_i)$ нь $A_i$-аас үзэгдэл тохиолдох магадлал бол тэдгээрийн нэгдлийн магадлал (өөрөөр хэлбэл үзэгдлүүдийн дор хаяж нэг нь тохиолдох магадлал) нь:

$$\begin{eqnarray} {\cal P} \left( \bigcup_{i=1}^n A_i \right) &=& \sum_{i=1}^n{\cal P}(A_i)\ - \sum_{1\leq i<j\leq n} {\cal P}(A_i \cap A_j)\ + \\ &+& \sum _{1\leq i<j<k\leq n}{\cal P}(A_i \cap A_j \cap A_k) - \cdots + (-1)^{n-1} {\cal P}( A_1 \cap \cdots \cap A_n ) \end{eqnarray}$$

Илүү товч байдлаар:

$${\cal P} \left(\bigcup_{i=1}^n A_i \right) = \sum_{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}} (-1)^{|J|-1}\ {\cal P}{\Biggl (}\bigcap_{j\in J}A_{j}{\Biggr )}$$

Баталгаа¶

Баталгааны хувьд олонлогийн онолын хэллэгээр математик томьёоллыг ашиглах нь тохиромжтой:

$$\left|\bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}} (-1)^{|J|-1}{\Biggl |}\bigcap_{j\in J}A_{j}{\Biggr |}$$

$A_i$ олонлогуудын дор хаяж нэгэнд агуулагдах дурын элемент томьёонд зөвхөн нэг удаа гарна гэдгийг батлахыг хүсэж байна ($A_i$ олонлогуудын алинд нь ч байхгүй элементүүдийг томьёоны баруун талд хэзээ ч авч үзэхгүй гэдгийг анхаарна уу).

$k \geq 1$ олонлог $A_i$-д гарч буй элемент $x$-г авч үзье. Түүнийг томьёонд зөвхөн нэг удаа тоолохыг бид харуулна. Дараахыг анхаарна уу:

$|J| = 1$ байх гишүүдэд элемент $x$-г $+\ k$ удаа тоолно;
$|J| = 2$ байх гишүүдэд элемент $x$-г $-\ \binom{k}{2}$ удаа тоолно — учир нь түүнийг $x$-г агуулах $k$ олонлогийн хоёрыг агуулах тэдгээр гишүүдэд тоолно;
$|J| = 3$ байх гишүүдэд элемент $x$-г $+\ \binom{k}{3}$ удаа тоолно;
$\cdots$
$|J| = k$ байх гишүүдэд элемент $x$-г $(-1)^{k-1}\cdot \binom{k}{k}$ удаа тоолно;
$|J| \gt k$ байх гишүүдэд элемент $x$-г тэг удаа тоолно;

Энэ нь биднийг дараах биномын коэффициент-үүдийн нийлбэрт хүргэнэ:

$$ T = \binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots + (-1)^{i-1}\cdot \binom{k}{i} + \cdots + (-1)^{k-1}\cdot \binom{k}{k}$$

Энэ илэрхийлэл нь $(1 - x)^k$-ийн биномын задаргаатай маш төстэй:

$$ (1 - x)^k = \binom{k}{0} - \binom{k}{1} \cdot x + \binom{k}{2} \cdot x^2 - \binom{k}{3} \cdot x^3 + \cdots + (-1)^k\cdot \binom{k}{k} \cdot x^k $$

$x = 1$ үед $(1 - x)^k$ нь $T$-тэй маш төстэй харагдана. Гэвч илэрхийлэлд нэмэлт $\binom{k}{0} = 1$ байгаа бөгөөд түүнийг $-1$-ээр үржүүлсэн. Энэ нь биднийг $(1 - 1)^k = 1 - T$ рүү хүргэнэ. Тиймээс $T = 1 - (1 - 1)^k = 1$ бөгөөд энэ нь батлах шаардлагатай зүйл байсан. Элементийг зөвхөн нэг удаа тоолно.

Яг $r$ олонлогт байгаа элементийн тоог тооцоолох ерөнхийлөл¶

Оруулах-хасах зарчмыг тэг олонлогт байгаа элементийн тоог тооцоолохоор дахин бичиж болно:

$$\left|\bigcap_{i=1}^n \overline{A_i}\right|=\sum_{m=0}^n (-1)^m \sum_{|X|=m} \left|\bigcap_{i\in X} A_{i}\right|$$

Яг $r$ олонлогт байгаа элементийн тоог тооцоолох түүний ерөнхийлөлийг авч үзье:

$$\left|\bigcup_{|B|=r}\left[\bigcap_{i \in B} A_i \cap \bigcap_{j \not\in B} \overline{A_j}\right]\right|=\sum_{m=r}^n (-1)^{m-r}\dbinom{m}{r} \sum_{|X|=m} \left|\bigcap_{i \in X} A_{i}\right|$$

Энэ томьёог батлахын тулд ямар нэг тодорхой $B$-г авч үзье. Үндсэн оруулах-хасах зарчмаар бид түүний талаар дараахыг хэлж болно:

$$\left|\bigcap_{i \in B} A_i \cap \bigcap_{j \not \in B} \overline{A_j}\right|=\sum_{m=r}^{n} (-1)^{m-r} \sum_{\substack{|X|=m \newline B \subset X}}\left|\bigcap_{i\in X} A_{i}\right|$$

Зүүн тал дахь олонлогууд өөр өөр $B$-ийн хувьд огтлолцохгүй тул бид тэдгээрийг шууд нийлбэрлэж болно. Мөн дурын олонлог $X$ гарч ирвэл үргэлж $(-1)^{m-r}$ коэффициенттэй байх ба яг $\dbinom{m}{r}$ олонлог $B$-ийн хувьд гарч ирнэ гэдгийг тэмдэглэх хэрэгтэй.

Бодлого бодоход ашиглах нь¶

Оруулах-хасах зарчмыг хэрэглээг нь судлахгүйгээр ойлгоход хэцүү.

Эхлээд бид зарчмын хэрэглээг харуулсан хамгийн энгийн гурван даалгаврыг "цаасан дээр" авч үзэж, дараа нь оруулах-хасах зарчмгүйгээр бодоход хэцүү илүү практик бодлогуудыг авч үзнэ.

"Аргын тоо-г ол" гэж асуудаг даалгаврууд анхаарал татахуйц, учир нь тэдгээр нь заримдаа заавал экспоненциал биш, полином шийдэлд хүргэдэг.

Сэлгэмэл дээрх энгийн даалгавар¶

Даалгавар: $0$-ээс $9$ хүртэлх тоонуудын хэдэн сэлгэмэл эхний элемент нь $1$-ээс их, сүүлийнх нь $8$-аас бага байхаар оршдогийг тоол.

"Муу" сэлгэмэлүүдийн тоог буюу эхний элемент нь $\leq 1$ ба/эсвэл сүүлийнх нь $\geq 8$ байх сэлгэмэлүүдийн тоог тоолъё.

Эхний элемент нь $\leq 1$ байх сэлгэмэлүүдийн олонлогийг $X$, сүүлийн элемент нь $\geq 8$ байх сэлгэмэлүүдийн олонлогийг $Y$ гэж тэмдэглэе. Тэгвэл оруулах-хасах томьёоны дагуу "муу" сэлгэмэлүүдийн тоо нь:

$$ |X \cup Y| = |X| + |Y| - |X \cap Y| $$

Энгийн комбинаторик тооцооллын дараа бид:

$$ 2 \cdot 9! + 2 \cdot 9! - 2 \cdot 2 \cdot 8! $$

-д хүрнэ. Үлдсэн цорын ганц зүйл бол "сайн" сэлгэмэлүүдийн тоог олохын тулд энэ тоог нийт $10!$-аас хасах явдал юм.

(0, 1, 2) дараалал дээрх энгийн даалгавар¶

Даалгавар: тоо бүр дор хаяж нэг удаа гарах байдлаар зөвхөн $0,1,2$ тоонуудаас тогтох $n$ урттай хэдэн дараалал оршдогийг тоол.

Дахин урвуу бодлого руу хандъя, өөрөөр хэлбэл бид тоонуудын дор хаяж нэгийг агуулаагүй дарааллын тоог тооцоолно.

$i$ цифр гараагүй дарааллуудын олонлогийг $A_i (i = 0,1,2)$ гэж тэмдэглэе. "Муу" дарааллуудын тоон дээрх оруулах-хасах томьёо нь:

$$ |A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2| $$

$A_i$ бүрийн хэмжээ нь $2^n$, учир нь дараалал бүр зөвхөн хоёр цифр агуулж болно.
$A_i \cap A_j$ хос хосын огтлолцол бүрийн хэмжээ нь $1$-тэй тэнцүү, учир нь дараалал байгуулах ердөө нэг цифр байна.
Гурван олонлог бүгдийн огтлолцлын хэмжээ нь $0$-тэй тэнцүү, учир нь дараалал байгуулах цифр байхгүй.

Бид урвуу бодлогыг бодсон тул түүнийг нийт $3^n$ дараалалаас хасна:

$$3^n - (3 \cdot 2^n - 3 \cdot 1 + 0)$$

Дээд хязгаартай бүхэл тоон нийлбэрийн тоо¶

Дараах тэгшитгэлийг авч үзье:

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20$$

энд $0 \le x_i \le 8 ~ (i = 1,2,\ldots 6)$.

Даалгавар: тэгшитгэлийн шийдийн тоог тоол.

$x_i$ дээрх хязгаарлалтыг түр мартаж, энэ тэгшитгэлийн сөрөг биш шийдийн тоог зүгээр л тоолъё. Үүнийг Од ба таславч ашиглан амархан хийж болно: бид $20$ нэгжийн дарааллыг $6$ бүлэгт хуваахыг хүсэж байгаа бөгөөд энэ нь $5$ таславч ба $20$ од байрлуулахтай ижил:

$$N_0 = \binom{25}{5}$$

Одоо бид оруулах-хасах зарчмаар "муу" шийдийн тоог тооцоолно. "Муу" шийдүүд нь нэг буюу хэд хэдэн $x_i$ нь $9$-ээс их буюу тэнцүү байх шийдүүд юм.

$x_k \ge 9$, бусад бүх $x_i \ge 0 ~ (i \ne k)$ ($\ge 9$ байж ч болно, үгүй ч байж болно) байх шийдүүдийн олонлогийг $A_k ~ (k = 1,2\ldots 6)$ гэж тэмдэглэе. $A_k$-ийн хэмжээг тооцоолохын тулд бид дээрх хоёр догол мөрөнд бодсонтой үндсэндээ ижил комбинаторик бодлоготой боловч одоо нэгжүүдийн $9$ нь нүднүүдээс хасагдаж, тодорхой эхний бүлэгт харьяалагдана гэдгийг тэмдэглэе. Тиймээс:

$$ | A_k | = \binom{16}{5} $$

Үүнтэй адил $A_k$ ба $A_p$ ($k \ne p$-ийн хувьд) хоёр олонлогийн огтлолцлын хэмжээ нь:

$$ \left| A_k \cap A_p \right| = \binom{7}{5}$$

Гурван олонлог бүрийн огтлолцлын хэмжээ нь тэг, учир нь $20$ нэгж нь $9$-ээс их буюу тэнцүү гурав буюу түүнээс олон хувьсагчид хангалтгүй.

Энэ бүхнийг оруулах-хасах томьёонд нэгтгэж, урвуу бодлого бодсоныг харгалзан бид эцэст нь хариуг олж авна:

$$\binom{25}{5} - \left(\binom{6}{1} \cdot \binom{16}{5} - \binom{6}{2} \cdot \binom{7}{5}\right) $$

Үүнийг $0 \le x_i \le b$ хязгаарлалттайгаар $s$ болж нийлбэрлэгддэг $d$ тоонд амархан ерөнхийлж болно:

$$\sum_{i=0}^d (-1)^i \binom{d}{i} \binom{s+d-1-(b+1)i}{d-1}$$

Дээрхтэй адил бид сөрөг дээд индекстэй биномын коэффициентийг тэг гэж үзнэ.

Энэ бодлогыг мөн динамик программчлал эсвэл үүсгэгч функцээр бодож болохыг анхаарна уу. Оруулах-хасах хариуг $O(d)$ хугацаанд тооцоолно (биномын коэффициент зэрэг математик үйлдлийг тогтмол хугацаа гэж үзвэл), харин энгийн DP арга $O(ds)$ хугацаа авна.

Өгөгдсөн интервал дахь харилцан анхны тооны тоо¶

Даалгавар: $n$ ба $r$ гэсэн хоёр тоо өгөгдсөн үед $[1;r]$ интервал дахь n-тэй харилцан анхны (тэдгээрийн хамгийн их ерөнхий хуваагч $1$) бүхэл тооны тоог тоол.

Урвуу бодлогыг бодъё — $n$-тэй харилцан анхны биш тооны тоог тооцоол.

$n$-ийн анхны үржигдэхүүнүүдийг $p_i (i = 1\cdots k)$ гэж тэмдэглэнэ.

$[1;r]$ интервал дахь хэдэн тоо $p_i$-д хуваагдах вэ? Энэ асуултын хариу нь:

$$ \left\lfloor \frac{ r }{ p_i } \right\rfloor $$

Гэвч хэрэв бид эдгээр тоог зүгээр л нийлбэрлэвэл зарим тоог хэд хэдэн удаа нийлбэрлэнэ (үржигдэхүүн болгон хэд хэдэн $p_i$-г хуваалцдаг тэдгээр). Тиймээс оруулах-хасах зарчмыг ашиглах шаардлагатай.

Бид $p_i$-ийн бүх $2^k$ дэд олонлогоор давтаж, тэдгээрийн үржвэрийг тооцоолж, тэдгээрийн үржвэрийн үржвэрүүдийн тоог нэмэх буюу хасна.

C++ хэрэгжүүлэлт энд байна:

int solve (int n, int r) {
    vector<int> p;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            p.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        p.push_back (n);

    int sum = 0;
    for (int msk=1; msk<(1<<p.size()); ++msk) {
        int mult = 1,
            bits = 0;
        for (int i=0; i<(int)p.size(); ++i)
            if (msk & (1<<i)) {
                ++bits;
                mult *= p[i];
            }

        int cur = r / mult;
        if (bits % 2 == 1)
            sum += cur;
        else
            sum -= cur;
    }

    return r - sum;
}

Шийдлийн асимптот нь $O (\sqrt{n})$.

Өгөгдсөн тоонуудын дор хаяж нэгийн үржвэр болох өгөгдсөн интервал дахь бүхэл тооны тоо¶

$n$ тоо $a_i$ ба $r$ тоо өгөгдсөн. Та $[1; r]$ интервал дахь $a_i$-ийн дор хаяж нэгийн үржвэр болох бүхэл тооны тоог тоолохыг хүсэж байна.

Шийдлийн алгоритм нь өмнөх даалгаврынхтай бараг ижил — $a_i$ тоонууд дээр оруулах-хасах томьёог байгуул, өөрөөр хэлбэл энэ томьёо дахь гишүүн бүр нь $a_i$ тоонуудын өгөгдсөн дэд олонлогт хуваагдах (өөрөөр хэлбэл тэдгээрийн хамгийн бага ерөнхий үржвэр-т хуваагдах) тоонуудын тоо юм.

Тиймээс бид одоо $a_i$ бүхэл тоонуудын бүх $2^n$ дэд олонлогоор давтаж, тэдгээрийн хамгийн бага ерөнхий үржвэрийг олох $O(n \log r)$ үйлдлээр, интервал дахь түүний үржвэрүүдийн тоог нэмэх буюу хасна. Асимптот нь $O (2^n\cdot n\cdot \log r)$.

Өгөгдсөн хэв маягийг хангах тэмдэгт мөрийн тоо¶

Зөвхөн үсэг ($a...z$) буюу асуултын тэмдэгтээс тогтох ижил урттай $n$ тэмдэгт мөрийн хэв маягийг авч үзье. Танд мөн $k$ тоо өгөгдсөн. Тэмдэгт мөр нь хэв маягтай ижил урттай бөгөөд байрлал бүрд харгалзах тэмдэгтүүд тэнцүү, эсвэл хэв маяг дахь тэмдэгт асуултын тэмдэгт байвал тэмдэгт мөр хэв маягтай тохирно. Даалгавар нь яг $k$ хэв маягтай тохирох (эхний бодлого) ба дор хаяж $k$ хэв маягтай тохирох (хоёр дахь бодлого) тэмдэгт мөрийн тоог тоолох явдал юм.

Эхлээд бид заасан бүх хэв маягийг нэг зэрэг хангах тэмдэгт мөрийн тоог амархан тоолж болохыг анзаарна. Үүний тулд хэв маягуудыг зүгээр л "огтлол": байрлалуудаар ("нүд") давтаж, бүх хэв маягийн хувьд байрлалыг хар. Хэрэв бүх хэв маяг энэ байрлалд асуултын тэмдэгттэй бол тэмдэгт нь $a$-аас $z$ хүртэлх дурын үсэг байж болно. Эс бөгөөс энэ байрлалын тэмдэгт нь асуултын тэмдэгт агуулаагүй хэв маягуудаар цор ганцаар тодорхойлогдоно.

Одоо бодлогын эхний хувилбарыг бодож сурцгаая: тэмдэгт мөр яг $k$ хэв маягийг хангах ёстой үед.

Үүнийг бодохын тулд $k$ хэв маягаас тогтох хэв маягуудын олонлогоос тодорхой дэд олонлог $X$-г давтаж тогтоо. Тэгвэл бид энэ хэв маягуудын олонлогийг хангах бөгөөд зөвхөн түүнтэй тохирох буюу өөр ямар ч хэв маягтай тохирохгүй тэмдэгт мөрийн тоог тоолох ёстой. Бид оруулах-хасах зарчмыг арай өөр байдлаар ашиглана: бид бүх дээд олонлог $Y$ ($X$-г агуулах анхны тэмдэгт мөрийн олонлогоос дэд олонлог)-ээр нийлбэрлэж, тэмдэгт мөрийн тооноос одоогийн хариуд нэмэх буюу хасна:

$$ ans(X) = \sum_{Y \supseteq X} (-1)^{|Y|-k} \cdot f(Y) $$

Энд $f(Y)$ нь $Y$-тэй (дор хаяж $Y$) тохирох тэмдэгт мөрийн тоо юм.

(Хэрэв танд үүнийг ойлгоход хэцүү байвал Венн диаграм зурж үзэж болно.)

Хэрэв бид бүх $ans(X)$-г нийлбэрлэвэл бид эцсийн хариуг олж авна:

$$ ans = \sum_{X ~ : ~ |X| = k} ans(X) $$

Гэвч энэ шийдлийн асимптот нь $O(3^k \cdot k)$. Үүнийг сайжруулахын тулд өөр өөр $ans(X)$ тооцоолол нь маш олон удаа $Y$ олонлогуудыг хуваалцдгийг анзаар.

Бид оруулах-хасах томьёог урвуулж, $Y$ олонлогуудын хэллэгээр нийлбэрлэнэ. Одоо ижил олонлог $Y$-г ижил тэмдэг $(-1)^{|Y| - k}$-тэйгээр $\binom{|Y|}{k}$ олонлогийн $ans(X)$-г тооцоолоход харгалзан үзэх нь тодорхой болно.

$$ ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot \binom{|Y|}{k} \cdot f(Y) $$

Одоо манай шийдэл $O(2^k \cdot k)$ асимптоттой болно.

Одоо бид бодлогын хоёр дахь хувилбарыг бодно: дор хаяж $k$ хэв маягтай тохирох тэмдэгт мөрийн тоог ол.

Мэдээж бид зүгээр л бодлогын эхний хувилбарын шийдлийг ашиглаж, $k$-аас их хэмжээтэй олонлогуудын хариуг нэмж болно. Гэвч энэ бодлогод $Y$-д агуулагдах $\ge k$ хэмжээтэй бүх олонлогийн хувьд олонлог |Y|-г томьёонд харгалзан үздгийг та анзаарч болно. Иймд бид $f(Y)$-ээр үржүүлж буй илэрхийллийн хэсгийг дараах байдлаар бичиж болно:

$$ (-1)^{|Y|-k} \cdot \binom{|Y|}{k} + (-1)^{|Y|-k-1} \cdot \binom{|Y|}{k+1} + (-1)^{|Y|-k-2} \cdot \binom{|Y|}{k+2} + \cdots + (-1)^{|Y|-|Y|} \cdot \binom{|Y|}{|Y|} $$

Грэмийн ном (Graham, Knuth, Patashnik. "Concrete mathematics" [1998])-ыг харвал бид биномын коэффициент-ийн сайн мэдэгдэх томьёог харна:

$$ \sum_{k=0}^m (-1)^k \cdot \binom{n}{k} = (-1)^m \cdot \binom{n-1}{m} $$

Үүнийг энд хэрэглэвэл бид биномын коэффициентүүдийн бүхэл нийлбэр хялбарчлагдахыг олно:

$$ (-1)^{|Y|-k} \cdot \binom{|Y|-1}{|Y|-k} $$

Тиймээс энэ даалгаврын хувьд бид мөн $O(2^k \cdot k)$ асимптоттой шийдэл олж авлаа:

$$ ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot \binom{|Y|-1}{|Y|-k} \cdot f(Y) $$

Нэг нүднээс өөр нүд рүү явах аргын тоо¶

$n \times m$ талбар байгаа бөгөөд түүний $k$ нүд нь нэвтэршгүй хана юм. Робот эхэндээ $(1,1)$ нүдэнд (зүүн доод) байна. Робот зөвхөн баруун эсвэл дээш хөдөлж болох ба эцэст нь бүх саадаас зайлсхийж $(n,m)$ нүдэнд очих хэрэгтэй. Түүний үүнийг хийж болох аргын тоог тоолох хэрэгтэй.

$n$ ба $m$ хэмжээ маш том (жишээ нь $10^9$), $k$ тоо бага (ойролцоогоор $100$) гэж үзье.

Одоохондоо саадуудыг $x$ координатаар нь, тэнцүү тохиолдолд $y$ координатаар нь эрэмбэл.

Мөн саадгүй бодлого хэрхэн бодохыг зүгээр л сурцгаая: өөрөөр хэлбэл нэг нүднээс өөр нүд рүү очих аргын тоог хэрхэн тоолохыг сур. Нэг тэнхлэгт бид $x$ нүд, нөгөөд $y$ нүд туулах хэрэгтэй. Энгийн комбинаторикоос бид биномын коэффициент ашигласан томьёог олж авна:

$$\binom{x+y}{x}$$

Одоо бүх саадаас зайлсхийж нэг нүднээс өөр нүд рүү очих аргын тоог тоолохын тулд та урвуу бодлого бодоход оруулах-хасахыг ашиглаж болно: саадуудын дэд олонлог дээр гишгэж самбараар алхах аргын тоог тоол (мөн түүнийг нийт аргын тооноос хас).

Бид гишгэх саадуудын дэд олонлогоор давтахдаа үүнийг хийх аргын тоог тоолохын тулд эхлэх нүднээс сонгосон саадуудын эхнийх хүртэлх, эхний саадаас хоёр дахь хүртэлх гэх мэт бүх замын тоог зүгээр л үржүүлж, дараа нь оруулах-хасах стандарт томьёоны дагуу энэ тоог хариунаас нэмэх буюу хасна.

Гэвч энэ нь дахин $O(2^k \cdot k)$ complexity-тэй полином биш болно.

Полином шийдэл энд байна:

Бид динамик программчлал ашиглана. Тав тухтай байлгах үүднээс саадуудын массивын эхэнд (1,1)-г, төгсгөлд (n,m)-г нэм. $d[i]$ тоонуудыг буюу эхлэх цэгээс ($0$-р) $i$-р хүртэл өөр ямар ч саад дээр гишгэлгүйгээр (мэдээж $i$-ээс бусад) очих аргын тоог тооцоолъё. Бид энэ тоог бүх саадын нүдний хувьд, мөн төгсгөлийн нүдний хувьд тооцоолно.

Түр зуур саадуудыг мартаж, зүгээр л $0$ нүднээс $i$ рүү очих замын тоог тоолъё. Бид зарим "муу" зам буюу саадуудаар дайрч өнгөрдөг замуудыг авч үзэж, $0$-ээс $i$ рүү явах нийт аргын тооноос хасах хэрэгтэй.

$0$ ба $i$-ийн хооронд ($0 < t < i$), бид гишгэж болох саад $t$-г авч үзэхэд бид $t$ дундуур дайрдаг, $t$-г эхлэл ба $i$-ийн хоорондох эхний саад болгосон $0$-ээс $i$ рүү очих замын тоог харна. Үүнийг бид: $d[t]$-г $t$-ээс $i$ рүү очих дурын замын тоогоор үржүүлж тооцоолж болно. Бид үүнийг $0$ ба $i$-ийн хоорондох бүх $t$-ийн хувьд нийлбэрлэж "муу" аргын тоог тоолж болно.

Бид $d[i]$-г $O(k)$ саадын хувьд $O(k)$-д тооцоолж чадах тул энэ шийдэл $O(k^2)$ complexity-тэй.

Харилцан анхны дөрвөлийн тоо¶

Танд $n$ тоо өгөгдсөн: $a_1, a_2, \ldots, a_n$. Тэдгээрийн нэгдсэн хамгийн их ерөнхий хуваагч нэгтэй тэнцүү байхаар дөрвөн тоо сонгох аргын тоог тоолох шаардлагатай.

Бид урвуу бодлогыг бодно — "муу" дөрвөлийн тоо буюу бүх тоо нь ямар нэг тоо $d > 1$-д хуваагдах дөрвөлийн тоог тооцоолно.

Бид хуваагч $d$-д хуваагдах дөрвөн тооны бүх боломжит бүлгээр нийлбэрлэхдээ оруулах-хасах зарчмыг ашиглана.

$$ans = \sum_{d \ge 2} (-1)^{deg(d)-1} \cdot f(d)$$

энд $deg(d)$ нь $d$ тооны задаргаа дахь анхны тоонуудын тоо, $f(d)$ нь $d$-д хуваагдах дөрвөлийн тоо юм.

$f(d)$ функцийг тооцоолохын тулд та зүгээр л $d$-ийн үржвэрүүдийн тоог тоолж (өмнөх даалгаварт дурдсанчлан), тэдгээрийн дөрвийг сонгох аргын тоог тоолохын тулд биномын коэффициент ашиглах хэрэгтэй.

Тиймээс оруулах-хасах томьёог ашиглан бид анхны тоонд хуваагдах дөрвийн бүлгийн тоог нийлбэрлэж, дараа нь хоёр анхны тооны үржвэрт хуваагдах дөрвөлийн тоог хасаж, гурван анхны тоонд хуваагдах дөрвөлийг нэмэх гэх мэт.

Гармоник гурвалын тоо¶

Танд $n \le 10^6$ тоо өгөгдсөн. Дараах нөхцөлүүдийн нэгийг хангах $2 \le a < b < c \le n$ гурвалын тоог тоолох шаардлагатай:

эсвэл ${\rm gcd}(a,b) = {\rm gcd}(a,c) = {\rm gcd}(b,c) = 1$,
эсвэл ${\rm gcd}(a,b) > 1, {\rm gcd}(a,c) > 1, {\rm gcd}(b,c) > 1$.

Эхлээд шууд урвуу бодлого руу оръё — өөрөөр хэлбэл гармоник биш гурвалын тоог тоол.

Хоёрдугаарт, дурын гармоник биш гурвал нь харилцан анхны хос ба хосын дор хаяж нэгтэй харилцан анхны биш гурав дахь тооноос тогтдгийг тэмдэглэ.

Тиймээс $i$-г агуулах гармоник биш гурвалын тоо нь $2$-оос $n$ хүртэлх $i$-тэй харилцан анхны бүхэл тоонуудын тоог $i$-тэй харилцан анхны биш бүхэл тоонуудын тоогоор үржүүлсэнтэй тэнцүү.

Эсвэл $gcd(a,b) = 1 \wedge gcd(a,c) > 1 \wedge gcd(b,c) > 1$

эсвэл $gcd(a,b) = 1 \wedge gcd(a,c) = 1 \wedge gcd(b,c) > 1$

Эдгээр хоёр тохиолдол хоёуланд нь үүнийг хоёр удаа тоолно. Эхний тохиолдлыг $i = a$ ба $i = b$ үед тоолно. Хоёр дахь тохиолдлыг $i = b$ ба $i = c$ үед тоолно. Тиймээс гармоник биш гурвалын тоог тооцоолохын тулд бид энэ тооцооллыг $2$-оос $n$ хүртэлх бүх $i$-ээр нийлбэрлэж, $2$-т хуваана.

Одоо бидний бодох ёстой цорын ганц зүйл бол $[2;n]$ интервал дахь $i$-тэй харилцан анхны тооны тоог тоолж сурах явдал юм. Энэ бодлогыг аль хэдийн дурдсан ч дээрх шийдэл энд тохиромжгүй — энэ нь $2$-оос $n$ хүртэлх бүхэл тоо бүрийг үржигдэхүүнд задлах, дараа нь эдгээр анхны тоонуудын бүх дэд олонлогоор давтахыг шаардана.

Эратосфены шигшүүрийн ийм өөрчлөлтөөр илүү хурдан шийдэл боломжтой:

Эхлээд бид $[2;n]$ интервалд анхны үржигдэхүүнд задаргаа нь анхны үржигдэхүүнийг хоёр удаа агуулаагүй бүх тоог олно. Мөн эдгээр тооны хувьд хэдэн үржигдэхүүн агуулдгийг мэдэх хэрэгтэй.
- Үүний тулд бид $i$-ийн задаргаа дахь анхны тоонуудын тоог хадгалах $deg[i]$ массив, $i$ нь үржигдэхүүн бүрийг хамгийн ихдээ нэг удаа агуулах ($good[i] = 1$) эсэх ($good[i] = 0$)-ийг тэмдэглэх $good[i]$ массивыг хадгална. $2$-оос $n$ хүртэл давтахдаа хэрэв бид $deg$ нь $0$-тэй тэнцүү тоонд хүрвэл энэ нь анхны тоо бөгөөд түүний $deg$ нь $1$ болно.
- Эратосфены шигшүүрийн явцад бид $i$-г $2$-оос $n$ хүртэл давтана. Анхны тоог боловсруулахдаа бид түүний бүх үржвэрээр явж, тэдгээрийн $deg[]$-г нэмэгдүүлнэ. Хэрэв эдгээр үржвэрийн нэг нь $i$-ийн квадратын үржвэр бол бид $good$-г false болгож болно.
Хоёрдугаарт, бид $2$-оос $n$ хүртэлх бүх $i$-ийн хувьд хариу буюу $cnt[]$ массив — $i$-тэй харилцан анхны биш бүхэл тоонуудын тоог тооцоолох хэрэгтэй.
- Үүний тулд оруулах-хасах томьёо хэрхэн ажилладгийг сана — үнэн хэрэгтээ энд бид ижил ойлголтыг хэрэгжүүлнэ, гэхдээ урвуу логиктойгоор: бид бүрэлдэхүүн хэсгээр (задаргааны анхны тоонуудын үржвэр) давтаж, түүний үржвэр бүрийн оруулах-хасах томьёонд түүний гишүүнийг нэмэх буюу хасна.
- Тэгэхээр $good[i] = true$ байх буюу оруулах-хасах томьёонд оролцох $i$ тоог боловсруулж байна гэж бодъё. $i$-ийн үржвэр болох бүх тоогоор давтаж, тэдгээрийн $cnt[]$-ээс $\lfloor N/i \rfloor$-г нэмэх буюу хасна (тэмдэг нь $deg[i]$-ээс хамаарна: хэрэв $deg[i]$ сондгой бол бид нэмэх ёстой, эс бөгөөс хасна).

C++ хэрэгжүүлэлт энд байна:

int n;
bool good[MAXN];
int deg[MAXN], cnt[MAXN];

long long solve() {
    memset (good, 1, sizeof good);
    memset (deg, 0, sizeof deg);
    memset (cnt, 0, sizeof cnt);

    long long ans_bad = 0;
    for (int i=2; i<=n; ++i) {
        if (good[i]) {
            if (deg[i] == 0)  deg[i] = 1;
            for (int j=1; i*j<=n; ++j) {
                if (j > 1 && deg[i] == 1)
                    if (j % i == 0)
                        good[i*j] = false;
                    else
                        ++deg[i*j];
                cnt[i*j] += (n / i) * (deg[i]%2==1 ? +1 : -1);
            }
        }
        ans_bad += (cnt[i] - 1) * 1ll * (n-1 - cnt[i]);
    }

    return (n-1) * 1ll * (n-2) * (n-3) / 6 - ans_bad / 2;
}

Манай шийдлийн асимптот нь $O(n \log n)$, учир нь $n$ хүртэлх бараг тоо бүрийн хувьд бид үүрлэсэн давталтад $n/i$ итерац хийнэ.

Хөдлөшгүй цэггүй сэлгэмэлийн тоо (эмх замбараагүйжүүлэлт)¶

$n$ урттай хөдлөшгүй цэггүй сэлгэмэлийн тоо (өөрөөр хэлбэл ямар ч тоо $i$ нь $i$ байрлалд байхгүй — эмх замбараагүйжүүлэлт (derangement) гэж бас нэрлэдэг) нь дараах тоотой тэнцүү болохыг батал:

$$n! - \binom{n}{1} \cdot (n-1)! + \binom{n}{2} \cdot (n-2)! - \binom{n}{3} \cdot (n-3)! + \cdots \pm \binom{n}{n} \cdot (n-n)! $$

ба ойролцоогоор:

$$ \frac{ n! }{ e } $$

-тэй тэнцүү (хэрэв та энэ илэрхийллийг хамгийн ойрын бүхэл тоо болгон бүхэлчилбэл — та яг хөдлөшгүй цэггүй сэлгэмэлийн тоог олно)

$k$ ($1 \le k \le n$) байрлалд хөдлөшгүй цэгтэй (өөрөөр хэлбэл элемент $k$ нь $k$ байрлалд байх) $n$ урттай сэлгэмэлүүдийн олонлогийг $A_k$ гэж тэмдэглэе.

Одоо бид дор хаяж нэг хөдлөшгүй цэгтэй сэлгэмэлийн тоог тоолохын тулд оруулах-хасах томьёог ашиглана. Үүний тулд бид $A_i$ олонлогуудын огтлолцлын хэмжээг дараах байдлаар тоолж сурах хэрэгтэй:

$$\begin{eqnarray} \left| A_p \right| &=& (n-1)!\ , \\ \left| A_p \cap A_q \right| &=& (n-2)!\ , \\ \left| A_p \cap A_q \cap A_r \right| &=& (n-3)!\ , \\ \cdots , \end{eqnarray}$$

учир нь хэрэв бид хөдлөшгүй цэгийн тоо $x$-тэй тэнцүү гэдгийг мэдвэл бид сэлгэмэлийн $x$ элементийн байрлалыг мэдэх ба бусад бүх $(n-x)$ элементийг дурын газар байрлуулж болно.

Үүнийг оруулах-хасах томьёонд орлуулж, $n$ элементийн олонлогоос $x$ хэмжээтэй дэд олонлог сонгох аргын тоо нь $\binom{n}{x}$-тэй тэнцүү болохыг харгалзан бид дор хаяж нэг хөдлөшгүй цэгтэй сэлгэмэлийн тооны томьёог олж авна:

$$\binom{n}{1} \cdot (n-1)! - \binom{n}{2} \cdot (n-2)! + \binom{n}{3} \cdot (n-3)! - \cdots \pm \binom{n}{n} \cdot (n-n)! $$

Тэгвэл хөдлөшгүй цэггүй сэлгэмэлийн тоо нь:

$$n! - \binom{n}{1} \cdot (n-1)! + \binom{n}{2} \cdot (n-2)! - \binom{n}{3} \cdot (n-3)! + \cdots \pm \binom{n}{n} \cdot (n-n)! $$

-тэй тэнцүү. Энэ илэрхийллийг хялбарчилж бид хөдлөшгүй цэггүй сэлгэмэлийн тооны яг ба ойролцоо илэрхийллийг олж авна:

$$ n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!} \right ) \approx \frac{n!}{e} $$

(учир нь хаалт доторх нийлбэр нь $e^{-1}$-ийн Тейлорын цуваанд задаргааны эхний $n+1$ гишүүн юм)

Ижил төстэй бодлогыг ийм байдлаар бодож болохыг тэмдэглэх нь зүйтэй: хөдлөшгүй цэгүүд сэлгэмэлийн эхний $m$ элементийн дунд байхыг шаардах үед (бидний дөнгөж бодсон шиг бүгдийн дунд биш). Олж авсан томьёо нь дээр өгсөн яг томьёотой адил боловч $n$-ийн оронд $k$-ийн нийлбэр хүртэл явна.

Дасгал бодлогууд¶

Оруулах-хасах зарчмаар бодож болох даалгаваруудын жагсаалт: