عملیات روی چندجمله‌ای‌ها و سری‌ها¶
مسائل در برنامه‌نویسی رقابتی، به‌ویژه آن‌هایی که به نوعی با شمارش سروکار دارند، اغلب با کاهش مسئله به محاسبه چیزی روی چندجمله‌ای‌ها و سری‌های توانی صوری حل می‌شوند.
این موضوع شامل مفاهیمی مانند ضرب چندجمله‌ای، درون‌یابی و موارد پیچیده‌تر مانند لگاریتم و توان چندجمله‌ای‌ها می‌شود. در این مقاله، یک نمای کلی از چنین عملیات‌ها و رویکردهای رایج برای آنها ارائه شده است.
مفاهیم و حقایق اولیه¶
در این بخش، بیشتر بر تعاریف و ویژگی‌های «شهودی» عملیات‌های مختلف چندجمله‌ای تمرکز می‌کنیم. جزئیات فنی پیاده‌سازی و پیچیدگی‌های آنها در بخش‌های بعدی پوشش داده خواهد شد.
ضرب چندجمله‌ای¶
تعریف
چندجمله‌ای تک‌متغیره عبارتی به شکل $A(x) = a_0 + a_1 x + \dots + a_n x^n$ است.
مقادیر $a_0, \dots, a_n$ ضرایب چندجمله‌ای هستند که معمولاً از مجموعهای از اعداد یا ساختارهای عددمانند گرفته می‌شوند. در این مقاله، فرض می‌کنیم که ضرایب از یک میدان گرفته شده‌اند، به این معنی که عملیات جمع، تفریق، ضرب و تقسیم برای آنها به‌خوبی تعریف شده است (به جز تقسیم بر $0$) و عموماً رفتاری مشابه اعداد حقیقی دارند.
نمونه‌ای معمول از چنین میدانی، میدان باقیمانده‌ها به پیمانه عدد اول $p$ است.
برای سادگی، ما از عبارت تک‌متغیره صرف‌نظر می‌کنیم، زیرا این تنها نوع چندجمله‌ای است که در این مقاله در نظر می‌گیریم. همچنین هرجا که ممکن باشد، به‌جای $A(x)$ از $A$ استفاده خواهیم کرد که از زمینه مطلب قابل درک خواهد بود. فرض بر این است که یا $a_n \neq 0$ است یا $A(x)=0$.
تعریف
حاصل‌ضرب دو چندجمله‌ای با بسط دادن آن به عنوان یک عبارت حسابی تعریف می‌شود:
دنباله $c_0, c_1, \dots, c_{n+m}$ از ضرایب $C(x)$، کانولوشن $a_0, \dots, a_n$ و $b_0, \dots, b_m$ نامیده می‌شود.
تعریف
درجه یک چندجمله‌ای $A$ با $a_n \neq 0$ به صورت $\deg A = n$ تعریف می‌شود.
برای هماهنگی، درجه $A(x) = 0$ به صورت $\deg A = -\infty$ تعریف می‌شود.
با این تعریف، برای هر دو چندجمله‌ای $A$ و $B$ داریم $\deg AB = \deg A + \deg B$.
کانولوشن‌ها اساس حل بسیاری از مسائل شمارشی هستند.
Example
شما $n$ شیء از نوع اول و $m$ شیء از نوع دوم دارید.
اشیاء نوع اول به ترتیب دارای ارزش $a_1, \dots, a_n$ و اشیاء نوع دوم دارای ارزش $b_1, \dots, b_m$ هستند.
شما یک شیء از نوع اول و یک شیء از نوع دوم انتخاب می‌کنید. به چند روش می‌توان به مجموع ارزش $k$ رسید؟
راه حل
حاصل‌ضرب $(x^{a_1} + \dots + x^{a_n})(x^{b_1} + \dots + x^{b_m})$ را در نظر بگیرید. اگر آن را بسط دهید، هر تک‌جمله‌ای به یک زوج $(a_i, b_j)$ مربوط می‌شود و در ضریب جمله $x^{a_i+b_j}$ مشارکت می‌کند. به عبارت دیگر، پاسخ، ضریب $x^k$ در این حاصل‌ضرب است.
Example
شما یک تاس ۶ وجهی را $n$ بار پرتاب می‌کنید و نتایج همه پرتاب‌ها را با هم جمع می‌کنید. احتمال اینکه مجموع برابر $k$ شود چقدر است؟
راه حل
پاسخ برابر است با تعداد نتایجی که مجموعشان $k$ می‌شود، تقسیم بر تعداد کل نتایج که $6^n$ است.
تعداد نتایجی که مجموعشان $k$ می‌شود چقدر است؟ برای $n=1$، این را می‌توان با چندجمله‌ای $A(x) = x^1+x^2+\dots+x^6$ نمایش داد.
برای $n=2$، با استفاده از همان رویکرد مثال بالا، به این نتیجه می‌رسیم که این تعداد با چندجمله‌ای $(x^1+x^2+\dots+x^6)^2$ نمایش داده می‌شود.
بنابراین، پاسخ مسئله، ضریب $k$-ام در چندجمله‌ای $(x^1+x^2+\dots+x^6)^n$ تقسیم بر $6^n$ است.
ضریب $x^k$ در چندجمله‌ای $A(x)$ به طور خلاصه با $[x^k]A$ نشان داده می‌شود.
سری‌های توانی صوری¶
تعریف
یک سری توانی صوری یک مجموع بی‌نهایت به شکل $A(x) = a_0 + a_1 x + a_2 x^2 + \dots$ است که صرف‌نظر از ویژگی‌های همگرایی آن در نظر گرفته می‌شود.
به عبارت دیگر، وقتی ما به عنوان مثال مجموع $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots=2$ را در نظر می‌گیریم، منظورمان این است که وقتی تعداد جملات به بی‌نهایت میل می‌کند، این مجموع به $2$ همگرا می‌شود. با این حال، سری‌های صوری تنها بر اساس دنباله‌هایی که آنها را تشکیل می‌دهند، در نظر گرفته می‌شوند.
تعریف
حاصل‌ضرب سری‌های توانی صوری $A(x)$ و $B(x)$، نیز با بسط دادن آن به عنوان یک عبارت حسابی تعریف می‌شود:
که در آن ضرایب $c_0, c_1, \dots$ به عنوان مجموعهای متناهی تعریف می‌شوند
دنباله $c_0, c_1, \dots$ نیز کانولوشن $a_0, a_1, \dots$ و $b_0, b_1, \dots$ نامیده می‌شود، که این مفهوم را به دنباله‌های بی‌نهایت تعمیم می‌دهد.
بنابراین، چندجمله‌ای‌ها را می‌توان به عنوان سری‌های توانی صوری در نظر گرفت، اما با تعداد محدودی ضریب.
سری‌های توانی صوری نقش حیاتی در ترکیبیات شمارشی دارند، جایی که به عنوان توابع مولد برای دنباله‌های مختلف مطالعه می‌شوند. توضیح دقیق توابع مولد و شهود پشت آنها، متأسفانه، خارج از حوصله این مقاله است، بنابراین خواننده کنجکاو برای جزئیات بیشتر در مورد معنای ترکیبیاتی آنها به عنوان مثال به اینجا ارجاع داده می‌شود.
با این حال، به طور خیلی خلاصه اشاره می‌کنیم که اگر $A(x)$ و $B(x)$ توابع مولد برای دنباله‌هایی باشند که اشیائی را بر اساس تعداد «اتم‌ها» در آنها شمارش می‌کنند (مثلاً درخت‌ها بر اساس تعداد رأس‌ها)، آنگاه حاصل‌ضرب $A(x) B(x)$ اشیائی را شمارش می‌کند که می‌توانند به عنوان زوج‌هایی از اشیاء نوع $A$ و $B$ توصیف شوند، و شمارش بر اساس تعداد کل «اتم‌ها» در زوج انجام می‌شود.
Example
فرض کنید $A(x) = \sum\limits_{i=0}^\infty 2^i x^i$ بسته‌هایی از سنگ‌ها را شمارش می‌کند که هر سنگ به یکی از ۲ رنگ رنگ‌آمیزی شده است (بنابراین $2^i$ بسته به اندازه $i$ وجود دارد) و $B(x) = \sum\limits_{j=0}^{\infty} 3^j x^j$ بسته‌هایی از سنگ‌ها را شمارش می‌کند که هر سنگ به یکی از ۳ رنگ رنگ‌آمیزی شده است. آنگاه $C(x) = A(x) B(x) = \sum\limits_{k=0}^\infty c_k x^k$ اشیائی را شمارش می‌کند که می‌توانند به عنوان «دو بسته سنگ، بسته اول فقط از سنگ‌های نوع $A$ و بسته دوم فقط از سنگ‌های نوع $B$، با تعداد کل سنگ‌ها برابر $k$» برای $c_k$ توصیف شوند.
به روشی مشابه، برای برخی توابع دیگر روی سری‌های توانی صوری نیز معنای شهودی وجود دارد.
تقسیم طولانی چندجمله‌ای‌ها¶
مشابه اعداد صحیح، می‌توان تقسیم طولانی را برای چندجمله‌ای‌ها تعریف کرد.
تعریف
برای هر دو چندجمله‌ای $A$ و $B \neq 0$، می‌توان $A$ را به صورت زیر نمایش داد:
که در آن $R$ باقیمانده $A$ بر $B$ و $D$ خارج‌قسمت نامیده می‌شود.
با فرض $\deg A = n$ و $\deg B = m$، روش ساده برای انجام این کار استفاده از تقسیم طولانی است، که در طی آن شما $B$ را در تک‌جمله‌ای $\frac{a_n}{b_m} x^{n - m}$ ضرب کرده و از $A$ کم می‌کنید، تا زمانی که درجه $A$ از درجه $B$ کمتر شود. آنچه در پایان از $A$ باقی می‌ماند، باقیمانده خواهد بود (از این رو نام آن) و مجموع چندجمله‌ای‌هایی که در این فرآیند $B$ را در آنها ضرب کرده‌اید، خارج‌قسمت را تشکیل می‌دهد.
تعریف
اگر $A$ و $B$ به پیمانه $C$ باقیمانده یکسانی داشته باشند، گفته می‌شود که به پیمانه $C$ هم‌نهشت هستند، که به صورت زیر نشان داده می‌شود:
تقسیم طولانی چندجمله‌ای‌ها به دلیل خواص مهم بسیاری که دارد، مفید است:
-
$A$ مضربی از $B$ است اگر و تنها اگر $A \equiv 0 \pmod B$.
-
این نتیجه می‌دهد که $A \equiv B \pmod C$ اگر و تنها اگر $A-B$ مضربی از $C$ باشد.
-
به طور خاص، $A \equiv B \pmod{C \cdot D}$ نتیجه می‌دهد که $A \equiv B \pmod{C}$.
-
برای هر چندجمله‌ای خطی $x-r$ برقرار است که $A(x) \equiv A(r) \pmod{x-r}$.
-
این نتیجه می‌دهد که $A$ مضربی از $x-r$ است اگر و تنها اگر $A(r)=0$.
-
برای پیمانه $x^k$، داریم $A \equiv a_0 + a_1 x + \dots + a_{k-1} x^{k-1} \pmod{x^k}$.
توجه داشته باشید که تقسیم طولانی را نمی‌توان به درستی برای سری‌های توانی صوری تعریف کرد. در عوض، برای هر $A(x)$ که $a_0 \neq 0$ باشد، می‌توان یک سری توانی صوری معکوس $A^{-1}(x)$ تعریف کرد، به طوری که $A(x) A^{-1}(x) = 1$. این واقعیت، به نوبه خود، می‌تواند برای محاسبه نتیجه تقسیم طولانی برای چندجمله‌ای‌ها استفاده شود.
پیاده‌سازی پایه‌ای¶
اینجا می‌توانید پیاده‌سازی پایه‌ای جبر چندجمله‌ای‌ها را پیدا کنید.
این پیاده‌سازی از تمام عملیات‌های ساده و برخی متدهای مفید دیگر پشتیبانی می‌کند. کلاس اصلی poly<T> برای چندجمله‌ای‌ها با ضرایب از نوع T است.
تمام عملیات حسابی +، -، *، % و / پشتیبانی می‌شوند، که % و / به ترتیب برای باقیمانده و خارج‌قسمت در تقسیم اقلیدسی هستند.
همچنین کلاس modular<m> برای انجام عملیات حسابی روی باقیمانده‌ها به پیمانه عدد اول m وجود دارد.
توابع مفید دیگر:
deriv(): مشتق $P'(x)$ از $P(x)$ را محاسبه می‌کند.integr(): انتگرال نامعین $Q(x) = \int P(x)$ از $P(x)$ را به طوری که $Q(0)=0$ باشد، محاسبه می‌کند.inv(size_t n): $n$ ضریب اول $P^{-1}(x)$ را در $O(n \log n)$ محاسبه می‌کند.log(size_t n): $n$ ضریب اول $\ln P(x)$ را در $O(n \log n)$ محاسبه می‌کند.exp(size_t n): $n$ ضریب اول $\exp P(x)$ را در $O(n \log n)$ محاسبه می‌کند.pow(size_t k, size_t n): $n$ ضریب اول $P^{k}(x)$ را در $O(n \log nk)$ محاسبه می‌کند.deg(): درجه $P(x)$ را برمی‌گرداند.lead(): ضریب $x^{\deg P(x)}$ را برمی‌گرداند.resultant(poly<T> a, poly<T> b): برآیند $a$ و $b$ را در $O(|a| \cdot |b|)$ محاسبه می‌کند.bpow(T x, size_t n): مقدار $x^n$ را محاسبه می‌کند.bpow(T x, size_t n, T m): مقدار $x^n \pmod{m}$ را محاسبه می‌کند.chirpz(T z, size_t n): مقادیر $P(1), P(z), P(z^2), \dots, P(z^{n-1})$ را در $O(n \log n)$ محاسبه می‌کند.vector<T> eval(vector<T> x): مقادیر $P(x_1), \dots, P(x_n)$ را در $O(n \log^2 n)$ مقداردهی می‌کند.poly<T> inter(vector<T> x, vector<T> y): یک چندجمله‌ای را از طریق مجموعهای از زوج‌های $P(x_i) = y_i$ در $O(n \log^2 n)$ درون‌یابی می‌کند.- و چند تابع دیگر، برای کاوش کد آزاد هستید!
حساب¶
ضرب¶
عملیات اصلی، ضرب دو چندجمله‌ای است. یعنی، با داشتن چندجمله‌ای‌های $A$ و $B$:
باید چندجمله‌ای $C = A \cdot B$ را محاسبه کنید، که به صورت زیر تعریف می‌شود:
این را می‌توان در $O(n \log n)$ از طریق تبدیل فوریه سریع (FFT) محاسبه کرد و تقریباً تمام روش‌های اینجا از آن به عنوان زیرروال استفاده می‌کنند.
سری معکوس¶
اگر $A(0) \neq 0$ باشد، همیشه یک سری توانی صوری بی‌نهایت $A^{-1}(x) = q_0+q_1 x + q_2 x^2 + \dots$ وجود دارد به طوری که $A^{-1} A = 1$. اغلب محاسبه $k$ ضریب اول $A^{-1}$ (یعنی محاسبه آن به پیمانه $x^k$) مفید است. دو راه اصلی برای محاسبه آن وجود دارد.
تقسیم و غلبه¶
این الگوریتم در مقاله Schönhage ذکر شده و از روش Graeffe الهام گرفته است. مشخص است که برای $B(x)=A(x)A(-x)$ داریم $B(x)=B(-x)$، یعنی $B(x)$ یک چندجمله‌ای زوج است. این به این معنی است که فقط ضرایب با توان‌های زوج آن غیرصفر هستند و می‌توان آن را به صورت $B(x)=T(x^2)$ نمایش داد. بنابراین، می‌توانیم انتقال زیر را انجام دهیم:
توجه داشته باشید که $T(x)$ را می‌توان با یک ضرب محاسبه کرد، و پس از آن ما فقط به نصف اول ضرایب سری معکوس آن علاقه‌مندیم. این به طور موثر مسئله اولیه محاسبه $A^{-1} \pmod{x^k}$ را به محاسبه $T^{-1} \pmod{x^{\lfloor k / 2 \rfloor}}$ کاهش می‌دهد.
پیچیدگی این روش را می‌توان به صورت زیر تخمین زد:
الگوریتم Sieveking–Kung¶
فرآیند کلی که در اینجا توصیف می‌شود به عنوان بالابری هنسل (Hensel lifting) شناخته می‌شود، زیرا از لم هنسل (Hensel's lemma) پیروی می‌کند. در ادامه به طور مفصل‌تر به آن خواهیم پرداخت، اما در حال حاضر بیایید روی یک راه حل موقت تمرکز کنیم. بخش «بالابری» در اینجا به این معنی است که ما با تقریب $B_0=q_0=a_0^{-1}$ شروع می‌کنیم، که همان $A^{-1} \pmod x$ است و سپس به طور تکراری از پیمانه $x^a$ به پیمانه $x^{2a}$ بالابری می‌کنیم.
فرض کنید $B_k \equiv A^{-1} \pmod{x^a}$. تقریب بعدی باید از معادله $A B_{k+1} \equiv 1 \pmod{x^{2a}}$ پیروی کند و می‌تواند به صورت $B_{k+1} = B_k + x^a C$ نمایش داده شود. از این، معادله زیر به دست می‌آید:
فرض کنید $A B_k \equiv 1 + x^a D \pmod{x^{2a}}$، آنگاه معادله بالا نتیجه می‌دهد:
از این، می‌توان فرمول نهایی را به دست آورد، که عبارت است از:
بنابراین با شروع از $B_0 \equiv a_0^{-1} \pmod x$ ما دنباله $B_k$ را به طوری که $AB_k \equiv 1 \pmod{x^{2^k}}$ با پیچیدگی زیر محاسبه خواهیم کرد:
الگوریتم اینجا ممکن است کمی پیچیده‌تر از الگوریتم اول به نظر برسد، اما یک استدلال بسیار محکم و عملی پشت آن وجود دارد، و همچنین اگر از منظر دیگری به آن نگاه شود، پتانسیل تعمیم بزرگی دارد که در ادامه توضیح داده خواهد شد.
تقسیم اقلیدسی¶
دو چندجمله‌ای $A(x)$ و $B(x)$ با درجات $n$ و $m$ را در نظر بگیرید. همانطور که قبلاً گفته شد، می‌توانید $A(x)$ را به صورت زیر بازنویسی کنید:
فرض کنید $n \geq m$، این به این معنی است که $\deg D = n - m$ و $n-m+1$ ضریب پیشرو $A$ بر $R$ تأثیری ندارند. این بدان معناست که شما می‌توانید $D(x)$ را از $n-m+1$ ضریب بزرگتر $A(x)$ و $B(x)$ بازیابی کنید، اگر آن را به عنوان یک دستگاه معادلات در نظر بگیرید.
دستگاه معادلات خطی که در مورد آن صحبت می‌کنیم را می‌توان به شکل زیر نوشت:
از ظاهر آن، می‌توان نتیجه گرفت که با معرفی چندجمله‌ای‌های معکوس‌شده
دستگاه را می‌توان به صورت زیر بازنویسی کرد:
از این می‌توانید به طور یکتا تمام ضرایب $D(x)$ را بازیابی کنید:
و از این، به نوبه خود، می‌توانید $R(x)$ را به عنوان $R(x) = A(x) - B(x)D(x)$ بازیابی کنید.
توجه داشته باشید که ماتریس بالا یک ماتریس به اصطلاح مثلثی Toeplitz است و همانطور که در اینجا می‌بینیم، حل دستگاه معادلات خطی با یک ماتریس Toeplitz دلخواه، در واقع، معادل با معکوس کردن چندجمله‌ای است. علاوه بر این، ماتریس معکوس آن نیز یک ماتریس Toeplitz مثلثی خواهد بود و درایه‌های آن، با اصطلاحات استفاده شده در بالا، ضرایب $(B^R(x))^{-1} \pmod{x^{n-m+1}}$ هستند.
محاسبه توابع چندجمله‌ای¶
روش نیوتن¶
بیایید الگوریتم Sieveking–Kung را تعمیم دهیم. معادله $F(P) = 0$ را در نظر بگیرید که در آن $P(x)$ باید یک چندجمله‌ای باشد و $F(x)$ یک تابع با مقادیر چندجمله‌ای است که به صورت زیر تعریف می‌شود:
که در آن $\beta$ یک ثابت است. می‌توان ثابت کرد که اگر یک متغیر صوری جدید $y$ را معرفی کنیم، می‌توانیم $F(x)$ را به صورت زیر بیان کنیم:
که در آن $F'(x)$ سری توانی صوری مشتق است که به صورت زیر تعریف می‌شود:
و $G(x, y)$ یک سری توانی صوری از $x$ و $y$ است. با این نتیجه می‌توانیم به طور تکراری راه حل را پیدا کنیم.
فرض کنید $F(Q_k) \equiv 0 \pmod{x^{a}}$. ما باید $Q_{k+1} \equiv Q_k + x^a C \pmod{x^{2a}}$ را پیدا کنیم به طوری که $F(Q_{k+1}) \equiv 0 \pmod{x^{2a}}$.
با جایگذاری $x = Q_{k+1}$ و $y=Q_k$ در فرمول بالا، داریم:
از آنجا که $Q_{k+1} - Q_k \equiv 0 \pmod{x^a}$، همچنین برقرار است که $(Q_{k+1} - Q_k)^2 \equiv 0 \pmod{x^{2a}}$، بنابراین
فرمول آخر مقدار $Q_{k+1}$ را به ما می‌دهد:
بنابراین، با دانستن چگونگی معکوس کردن چندجمله‌ای‌ها و چگونگی محاسبه $F(Q_k)$، می‌توانیم $n$ ضریب $P$ را با پیچیدگی زیر پیدا کنیم:
که در آن $f(n)$ زمان مورد نیاز برای محاسبه $F(Q_k)$ و $F'(Q_k)^{-1}$ است که معمولاً $O(n \log n)$ است.
قاعده تکرار بالا در تحلیل عددی به عنوان روش نیوتن شناخته می‌شود.
لم هنسل¶
همانطور که قبلاً ذکر شد، به طور صوری و عمومی این نتیجه به عنوان لم هنسل شناخته می‌شود و در واقع می‌تواند در معنای گسترده‌تری هنگامی که با یک سری از حلقه‌های تودرتو کار می‌کنیم، استفاده شود. در این مورد خاص، ما با دنباله‌ای از باقیمانده‌های چندجمله‌ای به پیمانه $x$، $x^2$، $x^3$ و غیره کار کردیم.
مثال دیگری که بالابری هنسل ممکن است مفید باشد، اعداد به اصطلاح p-adic هستند که در آن ما در واقع با دنباله‌ای از باقیمانده‌های صحیح به پیمانه $p$، $p^2$، $p^3$ و غیره کار می‌کنیم. به عنوان مثال، روش نیوتن می‌تواند برای یافتن همه اعداد خودریخت ممکن (اعدادی که هنگام به توان دو رسیدن به خود ختم می‌شوند) با یک مبنای عددی معین استفاده شود. این مسئله به عنوان یک تمرین برای خواننده باقی می‌ماند. شما می‌توانید مسئله این را در نظر بگیرید تا بررسی کنید که آیا راه حل شما برای اعداد مبنای ۱۰ کار می‌کند یا خیر.
لگاریتم¶
برای تابع $\ln P(x)$ می‌دانیم که:
بنابراین می‌توانیم $n$ ضریب $\ln P(x)$ را در $O(n \log n)$ محاسبه کنیم.
سری معکوس¶
معلوم می‌شود که می‌توانیم فرمول $A^{-1}$ را با استفاده از روش نیوتن به دست آوریم. برای این کار معادله $A=Q^{-1}$ را در نظر می‌گیریم، بنابراین:
تابع نمایی¶
بیایید یاد بگیریم چگونه $e^{P(x)}=Q(x)$ را محاسبه کنیم. باید داشته باشیم $\ln Q = P$، بنابراین:
توان $k$-ام¶
اکنون باید $P^k(x)=Q$ را محاسبه کنیم. این کار را می‌توان از طریق فرمول زیر انجام داد:
توجه داشته باشید که شما می‌توانید لگاریتم‌ها و توابع نمایی را به درستی محاسبه کنید تنها اگر بتوانید یک $Q_0$ اولیه پیدا کنید.
برای یافتن آن، باید لگاریتم یا توان ضریب ثابت چندجمله‌ای را محاسبه کنید.
اما تنها راه معقول برای انجام این کار این است که اگر $P(0)=1$ برای $Q = \ln P$ باشد تا $Q(0)=0$ شود و اگر $P(0)=0$ برای $Q = e^P$ باشد تا $Q(0)=1$ شود.
بنابراین شما می‌توانید از فرمول بالا فقط در صورتی استفاده کنید که $P(0) = 1$ باشد. در غیر این صورت اگر $P(x) = \alpha x^t T(x)$ که در آن $T(0)=1$ است، می‌توانید بنویسید:
توجه داشته باشید که شما همچنین می‌توانید ریشه $k$-ام یک چندجمله‌ای را محاسبه کنید اگر بتوانید $\sqrt[k]{\alpha}$ را محاسبه کنید، به عنوان مثال برای $\alpha=1$.
مقداردهی و درون‌یابی¶
تبدیل Chirp-z¶
برای حالت خاصی که نیاز به مقداردهی یک چندجمله‌ای در نقاط $x_r = z^{2r}$ دارید، می‌توانید کار زیر را انجام دهید:
بیایید $2kr = r^2+k^2-(r-k)^2$ را جایگزین کنیم. آنگاه این مجموع به صورت زیر بازنویسی می‌شود:
که تا ضریب $z^{r^2}$ برابر با کانولوشن دنباله‌های $u_k = a_k z^{k^2}$ و $v_k = z^{-k^2}$ است.
توجه داشته باشید که $u_k$ در اینجا اندیس‌هایی از $0$ تا $n$ دارد و $v_k$ اندیس‌هایی از $-n$ تا $m$ دارد که $m$ حداکثر توانی از $z$ است که شما نیاز دارید.
حال اگر نیاز به مقداردهی یک چندجمله‌ای در نقاط $x_r = z^{2r+1}$ دارید، می‌توانید آن را با تبدیل $a_k \to a_k z^k$ به مسئله قبلی کاهش دهید.
این به ما یک الگوریتم $O(n \log n)$ می‌دهد وقتی نیاز به محاسبه مقادیر در توان‌های $z$ دارید، بنابراین می‌توانید DFT را برای اندازه‌هایی که توان دو نیستند محاسبه کنید.
مشاهده دیگر این است که $kr = \binom{k+r}{2} - \binom{k}{2} - \binom{r}{2}$. آنگاه داریم:
ضریب $x^{n+r}$ در حاصل‌ضرب چندجمله‌ای‌های $A_0(x) = \sum\limits_{k=0}^n a_{n-k}z^{-\binom{n-k}{2}}x^k$ و $A_1(x) = \sum\limits_{k\geq 0}z^{\binom{k}{2}}x^k$ برابر با $z^{\binom{r}{2}}A(z^r)$ است. شما می‌توانید از فرمول $z^{\binom{k+1}{2}}=z^{\binom{k}{2}+k}$ برای محاسبه ضرایب $A_0(x)$ و $A_1(x)$ استفاده کنید.
مقداردهی چندنقطه‌ای¶
فرض کنید باید $A(x_1), \dots, A(x_n)$ را محاسبه کنید. همانطور که قبلاً ذکر شد، $A(x) \equiv A(x_i) \pmod{x-x_i}$. بنابراین می‌توانید کار زیر را انجام دهید:
- یک درخت بازه بسازید به طوری که در بازه $[l,r)$ حاصل‌ضرب $P_{l, r}(x) = (x-x_l)(x-x_{l+1})\dots(x-x_{r-1})$ قرار گیرد.
- با شروع از $l=1$ و $r=n+1$ در گره ریشه. فرض کنید $m=\lfloor(l+r)/2\rfloor$. با چندجمله‌ای $A(x) \pmod{P_{l,m}(x)}$ به سمت $[l,m)$ پایین بروید.
- این کار به صورت بازگشتی $A(x_l), \dots, A(x_{m-1})$ را محاسبه می‌کند، اکنون همین کار را برای $[m,r)$ با $A(x) \pmod{P_{m,r}(x)}$ انجام دهید.
- نتایج فراخوانی‌های بازگشتی اول و دوم را به هم بچسبانید و آنها را برگردانید.
کل این فرآیند در $O(n \log^2 n)$ اجرا خواهد شد.
درون‌یابی¶
یک فرمول مستقیم توسط لاگرانژ برای درون‌یابی یک چندجمله‌ای، با داشتن مجموعهای از زوج‌های $(x_i, y_i)$ وجود دارد:
محاسبه مستقیم آن کار سختی است اما معلوم می‌شود که می‌توانیم آن را در $O(n \log^2 n)$ با یک رویکرد تقسیم و غلبه محاسبه کنیم:
$P(x) = (x-x_1)\dots(x-x_n)$ را در نظر بگیرید. برای دانستن ضرایب مخرج‌ها در $A(x)$ باید حاصل‌ضرب‌هایی مانند زیر را محاسبه کنیم:
اما اگر مشتق $P'(x)$ را در نظر بگیرید، خواهید دید که $P'(x_i) = P_i$. بنابراین می‌توانید $P_i$ها را از طریق مقداردهی در $O(n \log^2 n)$ محاسبه کنید.
اکنون الگوریتم بازگشتی را که روی همان درخت بازه مانند مقداردهی چندنقطه‌ای انجام می‌شود، در نظر بگیرید. این الگوریتم در برگ‌ها با مقدار $\dfrac{y_i}{P_i}$ در هر برگ شروع می‌شود.
وقتی از بازگشت برمی‌گردیم، باید نتایج را از رئوس چپ و راست به صورت $A_{l,r} = A_{l,m}P_{m,r} + P_{l,m} A_{m,r}$ ادغام کنیم.
به این ترتیب وقتی به ریشه برمی‌گردید، دقیقاً $A(x)$ را در آن خواهید داشت. کل این فرآیند نیز در $O(n \log^2 n)$ کار می‌کند.
ب.م.م و برآیندها¶
فرض کنید چندجمله‌ای‌های $A(x) = a_0 + a_1 x + \dots + a_n x^n$ و $B(x) = b_0 + b_1 x + \dots + b_m x^m$ به شما داده شده‌اند.
فرض کنید $\lambda_0, \dots, \lambda_n$ ریشه‌های $A(x)$ و $\mu_0, \dots, \mu_m$ ریشه‌های $B(x)$ با در نظر گرفتن تکرارشان باشند.
شما می‌خواهید بدانید آیا $A(x)$ و $B(x)$ ریشه مشترکی دارند یا خیر. دو راه به هم پیوسته برای انجام این کار وجود دارد.
الگوریتم اقلیدسی¶
خب، ما قبلاً یک مقاله در مورد آن داریم. برای یک دامنه دلخواه می‌توانید الگوریتم اقلیدسی را به سادگی به صورت زیر بنویسید:
template<typename T>
T gcd(const T &a, const T &b) {
return b == T(0) ? a : gcd(b, a % b);
}
می‌توان ثابت کرد که برای چندجمله‌ای‌های $A(x)$ و $B(x)$ این الگوریتم در $O(nm)$ کار خواهد کرد.
برآیند¶
بیایید حاصل‌ضرب $A(\mu_0)\cdots A(\mu_m)$ را محاسبه کنیم. این حاصل‌ضرب برابر با صفر خواهد بود اگر و تنها اگر یکی از $\mu_i$ها ریشه $A(x)$ باشد.
برای تقارن، می‌توانیم آن را در $b_m^n$ نیز ضرب کرده و کل حاصل‌ضرب را به شکل زیر بازنویسی کنیم:
مقدار تعریف شده در بالا، برآیند چندجمله‌ای‌های $A(x)$ و $B(x)$ نامیده می‌شود. از تعریف می‌توانید خواص زیر را پیدا کنید:
- $\mathcal R(A, B) = (-1)^{nm} \mathcal R(B, A)$.
- $\mathcal R(A, B)= a_n^m b_m^n$ وقتی $n=0$ یا $m=0$.
- اگر $b_m=1$ باشد، آنگاه $\mathcal R(A - CB, B) = \mathcal R(A, B)$ برای یک چندجمله‌ای دلخواه $C(x)$ و $n,m \geq 1$.
- از این نتیجه می‌شود $\mathcal R(A, B) = b_m^{\deg(A) - \deg(A-CB)}\mathcal R(A - CB, B)$ برای $A(x)$، $B(x)$، $C(x)$ دلخواه.
به طرز شگفت‌آوری این به این معنی است که برآیند دو چندجمله‌ای در واقع همیشه از همان حلقه‌ای است که ضرایب آنها از آن هستند!
همچنین این خواص به ما امکان می‌دهد که برآیند را در کنار الگوریتم اقلیدسی محاسبه کنیم، که در $O(nm)$ کار می‌کند.
template<typename T>
T resultant(poly<T> a, poly<T> b) {
if(b.is_zero()) {
return 0;
} else if(b.deg() == 0) {
return bpow(b.lead(), a.deg());
} else {
int pw = a.deg();
a %= b;
pw -= a.deg();
base mul = bpow(b.lead(), pw) * base((b.deg() & a.deg() & 1) ? -1 : 1);
base ans = resultant(b, a);
return ans * mul;
}
}
الگوریتم نیم-ب.م.م (Half-GCD)¶
راهی برای محاسبه ب.م.م و برآیندها در $O(n \log^2 n)$ وجود دارد.
روال انجام این کار یک تبدیل خطی $2 \times 2$ را پیاده‌سازی می‌کند که یک زوج از چندجمله‌ای‌های $a(x)$، $b(x)$ را به یک زوج دیگر $c(x), d(x)$ نگاشت می‌کند به طوری که $\deg d(x) \leq \frac{\deg a(x)}{2}$. اگر به اندازه کافی دقت کنید، می‌توانید نیم-ب.م.م هر زوج از چندجمله‌ای‌ها را با حداکثر ۲ فراخوانی بازگشتی به چندجمله‌ای‌هایی که حداقل ۲ برابر کوچکتر هستند، محاسبه کنید.
جزئیات خاص الگوریتم برای توضیح تا حدودی خسته‌کننده است، با این حال می‌توانید پیاده‌سازی آن را در کتابخانه، به عنوان تابع half_gcd پیدا کنید.
پس از پیاده‌سازی نیم-ب.م.م، می‌توانید آن را به طور مکرر روی چندجمله‌ای‌ها اعمال کنید تا به زوج $\gcd(a, b)$ و $0$ کاهش یابید.