পলিনোমিয়াল ও সিরিজের উপর অপারেশন#
প্রতিযোগিতামূলক প্রোগ্রামিংয়ের সমস্যাগুলো, বিশেষত যেগুলো কোনোভাবে গণনা সম্পর্কিত, প্রায়ই পলিনোমিয়াল ও ফর্মাল পাওয়ার সিরিজের উপর কিছু গণনায় সমস্যাটি সংকুচিত করে সমাধান করা হয়।
এর মধ্যে রয়েছে পলিনোমিয়াল গুণন, ইন্টারপোলেশন, এবং আরো জটিল ক্রিয়াকলাপ, যেমন পলিনোমিয়াল লগারিদম ও সূচকীয়। এই নিবন্ধে, এরকম অপারেশন ও তাদের সাধারণ পদ্ধতিগুলোর একটি সংক্ষিপ্ত পর্যালোচনা উপস্থাপন করা হয়েছে।
মৌলিক ধারণা ও তথ্য#
এই বিভাগে, আমরা বিভিন্ন পলিনোমিয়াল অপারেশনের সংজ্ঞা ও “স্বজ্ঞাত” বৈশিষ্ট্যের উপর বেশি মনোযোগ দেবো। তাদের ইমপ্লিমেন্টেশন ও কমপ্লেক্সিটির প্রযুক্তিগত বিবরণ পরবর্তী বিভাগে আলোচনা করা হবে।
পলিনোমিয়াল গুণন#
মান $a_0, \dots, a_n$ হলো পলিনোমিয়ালের সহগ, সাধারণত কোনো সংখ্যা বা সংখ্যা-সদৃশ কাঠামোর সেট থেকে নেওয়া। এই নিবন্ধে, আমরা ধরে নিচ্ছি সহগ কোনো ফিল্ড থেকে নেওয়া, অর্থাৎ যোগ, বিয়োগ, গুণন ও ভাগের অপারেশন তাদের জন্য সুসংজ্ঞায়িত ($0$ দিয়ে ভাগ ছাড়া) এবং তারা সাধারণভাবে বাস্তব সংখ্যার মতোই আচরণ করে।
এরকম ফিল্ডের সাধারণ উদাহরণ হলো মৌলিক সংখ্যা $p$ মডুলোতে ভাগশেষের ফিল্ড।
সরলতার জন্য আমরা একচলবিশিষ্ট শব্দটি বাদ দেবো, কারণ এই নিবন্ধে আমরা শুধু এই ধরনের পলিনোমিয়ালই বিবেচনা করি। প্রসঙ্গ থেকে বোঝা যাবে বলে সম্ভব হলে আমরা $A(x)$ এর বদলে $A$-ও লিখবো। ধরে নেওয়া হয় $a_n \neq 0$ অথবা $A(x)=0$।
$$
A(x) B(x) = \left(\sum\limits_{i=0}^n a_i x^i \right)\left(\sum\limits_{j=0}^m b_j x^j\right) = \sum\limits_{i,j} a_i b_j x^{i+j} = \sum\limits_{k=0}^{n+m} c_k x^k = C(x).
$$
$C(x)$ এর সহগ ক্রম $c_0, c_1, \dots, c_{n+m}$ কে $a_0, \dots, a_n$ ও $b_0, \dots, b_m$ এর **কনভোলিউশন** বলা হয়।
সামঞ্জস্যের জন্য, $A(x) = 0$ এর ডিগ্রি $\deg A = -\infty$ হিসেবে সংজ্ঞায়িত।
এই ধারণায়, যেকোনো পলিনোমিয়াল $A$ ও $B$ এর জন্য $\deg AB = \deg A + \deg B$।
কনভোলিউশন অনেক গণনামূলক সমস্যা সমাধানের ভিত্তি।
প্রথম ধরনের বস্তুগুলোর মান $a_1, \dots, a_n$, এবং দ্বিতীয় ধরনের বস্তুগুলোর মান $b_1, \dots, b_m$।
আপনি একটি প্রথম ধরনের ও একটি দ্বিতীয় ধরনের বস্তু বেছে নেন। মোট মান $k$ পাওয়ার কতগুলো উপায় আছে?
সমাধান
সমাধান
যোগফল $k$ হওয়া ফলাফলের সংখ্যা কত? $n=1$ এর জন্য, এটি $A(x) = x^1+x^2+\dots+x^6$ পলিনোমিয়াল দিয়ে উপস্থাপন করা যায়।
$n=2$ এর জন্য, উপরের উদাহরণের মতো একই পদ্ধতি ব্যবহার করে, আমরা সিদ্ধান্তে আসি এটি $(x^1+x^2+\dots+x^6)^2$ পলিনোমিয়াল দিয়ে উপস্থাপিত।
এজন্য, সমস্যার উত্তর হলো $(x^1+x^2+\dots+x^6)^n$ এর $k$-তম সহগকে $6^n$ দিয়ে ভাগ।
পলিনোমিয়াল $A(x)$ এ $x^k$ এর কাছের সহগকে সংক্ষেপে $[x^k]A$ দ্বারা চিহ্নিত করা হয়।
ফর্মাল পাওয়ার সিরিজ#
অন্য কথায়, যখন আমরা $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots=2$ এর মতো যোগফল বিবেচনা করি, আমরা বোঝাই যে পদসংখ্যা অসীমে গেলে এটি $2$ তে অভিসৃত হয়। তবে, ফর্মাল সিরিজ শুধু তাদের গঠনকারী ক্রমের পরিপ্রেক্ষিতেই বিবেচিত।
$$
A(x) B(x) = \left(\sum\limits_{i=0}^\infty a_i x^i \right)\left(\sum\limits_{j=0}^\infty b_j x^j\right) = \sum\limits_{i,j} a_i b_j x^{i+j} = \sum\limits_{k=0}^{\infty} c_k x^k = C(x),
$$
যেখানে সহগ $c_0, c_1, \dots$ সসীম যোগফল হিসেবে সংজ্ঞায়িত
$$
c_k = \sum\limits_{i=0}^k a_i b_{k-i}.
$$
ক্রম $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$ ধরনের বস্তুর জোড়া হিসেবে বর্ণনাযোগ্য বস্তু গণনা করে, জোড়ায় মোট “পরমাণু” সংখ্যা দিয়ে গণনা করে।
অনুরূপভাবে, ফর্মাল পাওয়ার সিরিজের উপর অন্য কিছু ফাংশনেরও স্বজ্ঞাত অর্থ আছে।
দীর্ঘ পলিনোমিয়াল ভাগ#
পূর্ণসংখ্যার মতোই, পলিনোমিয়ালের উপর দীর্ঘ ভাগ সংজ্ঞায়িত করা সম্ভব।
$$
A = D \cdot B + R,~ \deg R < \deg B,
$$
যেখানে $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 \equiv B \pmod{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_0 \neq 0$ বিশিষ্ট যেকোনো $A(x)$ এর জন্য, একটি বিপরীত ফর্মাল পাওয়ার সিরিজ $A^{-1}(x)$ সংজ্ঞায়িত করা সম্ভব, যেন $A(x) A^{-1}(x) = 1$। এই তথ্য পলিনোমিয়ালের দীর্ঘ ভাগের ফলাফল গণনা করতে ব্যবহার করা যায়।
মৌলিক ইমপ্লিমেন্টেশন#
এখানে আপনি পলিনোমিয়াল বীজগণিতের মৌলিক ইমপ্লিমেন্টেশন পাবেন।
এটি সব তুচ্ছ অপারেশন ও কিছু অন্যান্য কার্যকর মেথড সমর্থন করে। প্রধান ক্লাস হলো poly<T> T ধরনের সহগ বিশিষ্ট পলিনোমিয়ালের জন্য।
সব বীজগণিতীয় অপারেশন +, -, *, % ও / সমর্থিত, % ও / ইউক্লিডীয় ভাগে ভাগশেষ ও ভাগফলের জন্য।
একটি modular<m> ক্লাসও আছে মৌলিক সংখ্যা m মডুলোতে ভাগশেষের উপর বীজগণিতীয় অপারেশন করতে।
অন্যান্য কার্যকর ফাংশন:
deriv(): $P(x)$ এর ডেরিভেটিভ $P'(x)$ গণনা করে।integr(): $P(x)$ এর অনির্দিষ্ট সমাকলন $Q(x) = \int P(x)$ গণনা করে যেন $Q(0)=0$।inv(size_t n): $O(n \log n)$-এ $P^{-1}(x)$ এর প্রথম $n$ টি সহগ গণনা করে।log(size_t n): $O(n \log n)$-এ $\ln P(x)$ এর প্রথম $n$ টি সহগ গণনা করে।exp(size_t n): $O(n \log n)$-এ $\exp P(x)$ এর প্রথম $n$ টি সহগ গণনা করে।pow(size_t k, size_t n): $O(n \log nk)$-এ $P^{k}(x)$ এর প্রথম $n$ টি সহগ গণনা করে।deg(): $P(x)$ এর ডিগ্রি রিটার্ন করে।lead(): $x^{\deg P(x)}$ এর সহগ রিটার্ন করে।resultant(poly<T> a, poly<T> b): $O(|a| \cdot |b|)$-এ $a$ ও $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): $O(n \log n)$-এ $P(1), P(z), P(z^2), \dots, P(z^{n-1})$ গণনা করে।vector<T> eval(vector<T> x): $O(n \log^2 n)$-এ $P(x_1), \dots, P(x_n)$ মূল্যায়ন করে।poly<T> inter(vector<T> x, vector<T> y): $O(n \log^2 n)$-এ $P(x_i) = y_i$ জোড়ার সেট দিয়ে একটি পলিনোমিয়াল ইন্টারপোলেট করে।- এবং আরো, কোড অন্বেষণ করুন!
পাটিগণিত#
গুণন#
মূল অপারেশন হলো দুটি পলিনোমিয়ালের গুণন। অর্থাৎ, পলিনোমিয়াল $A$ ও $B$ দেওয়া আছে:
$$A = a_0 + a_1 x + \dots + a_n x^n$$$$B = b_0 + b_1 x + \dots + b_m x^m$$পলিনোমিয়াল $C = A \cdot B$ গণনা করতে হবে, যা এভাবে সংজ্ঞায়িত
$$\boxed{C = \sum\limits_{i=0}^n \sum\limits_{j=0}^m a_i b_j x^{i+j}} = c_0 + c_1 x + \dots + c_{n+m} x^{n+m}.$$এটি $O(n \log n)$-এ ফাস্ট ফুরিয়ার ট্রান্সফর্ম দিয়ে গণনা করা যায় এবং এখানকার প্রায় সব পদ্ধতি এটিকে সাবরুটিন হিসেবে ব্যবহার করবে।
বিপরীত সিরিজ#
যদি $A(0) \neq 0$ হয় তাহলে সবসময় একটি অসীম ফর্মাল পাওয়ার সিরিজ $A^{-1}(x) = q_0+q_1 x + q_2 x^2 + \dots$ থাকে যেন $A^{-1} A = 1$। $A^{-1}$ এর প্রথম $k$ সহগ গণনা (অর্থাৎ $x^k$ মডুলোতে গণনা) প্রায়ই কার্যকর। দুটি প্রধান উপায়ে এটি গণনা করা যায়।
বিভাজন ও জয়#
এই অ্যালগরিদম Schönhage-এর নিবন্ধে উল্লেখিত এবং Graeffe-এর পদ্ধতি দ্বারা অনুপ্রাণিত। এটি জানা যে $B(x)=A(x)A(-x)$ এর জন্য $B(x)=B(-x)$, অর্থাৎ $B(x)$ একটি জোড় পলিনোমিয়াল। এর মানে এতে শুধু জোড় সংখ্যক সহগ অশূন্য এবং একে $B(x)=T(x^2)$ আকারে উপস্থাপন করা যায়। সুতরাং, নিম্নলিখিত রূপান্তর করা যায়:
$$A^{-1}(x) \equiv \frac{1}{A(x)} \equiv \frac{A(-x)}{A(x)A(-x)} \equiv \frac{A(-x)}{T(x^2)} \pmod{x^k}$$লক্ষ্য করুন $T(x)$ একটি মাত্র গুণনে গণনা করা যায়, এরপর আমরা শুধু এর বিপরীত সিরিজের প্রথম অর্ধেক সহগেই আগ্রহী। এটি কার্যকরভাবে $A^{-1} \pmod{x^k}$ গণনার প্রাথমিক সমস্যাকে $T^{-1} \pmod{x^{\lceil k / 2 \rceil}}$ গণনায় সংকুচিত করে।
এই পদ্ধতির কমপ্লেক্সিটি অনুমান করা যায়
$$T(n) = T(n/2) + O(n \log n) = O(n \log n).$$সিভকিং-কুং অ্যালগরিদম#
এখানে বর্ণিত সাধারণ প্রক্রিয়া হেনসেল লিফটিং নামে পরিচিত, কারণ এটি হেনসেলের লেমা থেকে অনুসরণ করে। আমরা এটি পরে আরো বিস্তারিত আলোচনা করবো, কিন্তু আপাতত অ্যাড হক সমাধানে মনোযোগ দেই। এখানে “লিফটিং” অংশের মানে হলো আমরা আনুমানিক মান $B_0=q_0=a_0^{-1}$ দিয়ে শুরু করি, যা $A^{-1} \pmod x$ এবং তারপর পুনরাবৃত্তিমূলকভাবে $\bmod x^a$ থেকে $\bmod 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 + x^{a}C) \equiv 1 \pmod{x^{2a}}.$$ধরি $A B_k \equiv 1 + x^a D \pmod{x^{2a}}$, তাহলে উপরের সমীকরণ থেকে পাই
$$x^a(D+AC) \equiv 0 \pmod{x^{2a}} \implies D \equiv -AC \pmod{x^a} \implies C \equiv -B_k D \pmod{x^a}.$$এ থেকে চূড়ান্ত সূত্র পাওয়া যায়
$$x^a C \equiv -B_k x^a D \equiv B_k(1-AB_k) \pmod{x^{2a}} \implies \boxed{B_{k+1} \equiv B_k(2-AB_k) \pmod{x^{2a}}}$$সুতরাং $B_0 \equiv a_0^{-1} \pmod x$ থেকে শুরু করে আমরা $B_k$ ক্রম গণনা করবো যেন $AB_k \equiv 1 \pmod{x^{2^k}}$ কমপ্লেক্সিটিতে
$$T(n) = T(n/2) + O(n \log n) = O(n \log n).$$এখানকার অ্যালগরিদম প্রথমটির চেয়ে কিছুটা জটিল মনে হতে পারে, কিন্তু এর পেছনে অত্যন্ত মজবুত ও ব্যবহারিক যুক্তি আছে, সেইসাথে ভিন্ন দৃষ্টিকোণ থেকে দেখলে দুর্দান্ত সাধারণীকরণ সম্ভাবনা আছে, যা পরে ব্যাখ্যা করা হবে।
ইউক্লিডীয় ভাগ#
$n$ ও $m$ ডিগ্রির দুটি পলিনোমিয়াল $A(x)$ ও $B(x)$ বিবেচনা করুন। আগে বলা হয়েছে আপনি $A(x)$ কে এভাবে লিখতে পারেন
$$A(x) = B(x) D(x) + R(x), \deg R < \deg B.$$ধরি $n \geq m$, এটি বোঝায় $\deg D = n - m$ এবং $A$ এর বৃহত্তম $n-m+1$ সহগ $R$ কে প্রভাবিত করে না। অর্থাৎ আপনি $A(x)$ ও $B(x)$ এর বৃহত্তম $n-m+1$ সহগ থেকে $D(x)$ উদ্ধার করতে পারেন যদি এটিকে রৈখিক সমীকরণ ব্যবস্থা হিসেবে বিবেচনা করেন।
আমরা যে রৈখিক সমীকরণ ব্যবস্থার কথা বলছি তা নিম্নলিখিত আকারে লেখা যায়:
$$\begin{bmatrix} a_n \\ \vdots \\ a_{m+1} \\ a_{m} \end{bmatrix} = \begin{bmatrix} b_m & \dots & 0 & 0 \\ \vdots & \ddots & \vdots & \vdots \\ \dots & \dots & b_m & 0 \\ \dots & \dots & b_{m-1} & b_m \end{bmatrix} \begin{bmatrix}d_{n-m} \\ \vdots \\ d_1 \\ d_0\end{bmatrix}$$এর চেহারা থেকে, আমরা উপসংহার টানতে পারি যে বিপরীত পলিনোমিয়ালের প্রবর্তনে
$$A^R(x) = x^nA(x^{-1})= a_n + a_{n-1} x + \dots + a_0 x^n$$$$B^R(x) = x^m B(x^{-1}) = b_m + b_{m-1} x + \dots + b_0 x^m$$$$D^R(x) = x^{n-m}D(x^{-1}) = d_{n-m} + d_{n-m-1} x + \dots + d_0 x^{n-m}$$ব্যবস্থাটি এভাবে পুনঃলেখা যায়
$$A^R(x) \equiv B^R(x) D^R(x) \pmod{x^{n-m+1}}.$$এ থেকে আপনি $D(x)$ এর সব সহগ দ্ব্যর্থহীনভাবে উদ্ধার করতে পারেন:
$$\boxed{D^R(x) \equiv A^R(x) (B^R(x))^{-1} \pmod{x^{n-m+1}}}$$এবং এ থেকে, পালটা, $R(x) = A(x) - B(x)D(x)$ হিসেবে $R(x)$ উদ্ধার করা যায়।
লক্ষ্য করুন উপরের ম্যাট্রিক্সটি তথাকথিত ত্রিভুজাকার টোয়েপ্লিৎজ ম্যাট্রিক্স এবং, এখানে দেখা যাচ্ছে, যেকোনো টোয়েপ্লিৎজ ম্যাট্রিক্স দিয়ে রৈখিক সমীকরণ ব্যবস্থা সমাধান করা আসলে পলিনোমিয়াল বিপরীতকরণের সমতুল্য।
পলিনোমিয়ালের ফাংশন গণনা#
নিউটনের পদ্ধতি#
সিভকিং-কুং অ্যালগরিদমকে সাধারণীকরণ করা যাক। $F(P) = 0$ সমীকরণ বিবেচনা করুন যেখানে $P(x)$ একটি পলিনোমিয়াল হওয়া উচিত এবং $F(x)$ একটি পলিনোমিয়াল-মানবিশিষ্ট ফাংশন যা এভাবে সংজ্ঞায়িত
$$F(x) = \sum\limits_{i=0}^\infty \alpha_i (x-\beta)^i,$$যেখানে $\beta$ একটি ধ্রুবক। এটি প্রমাণ করা যায় যে নতুন ফর্মাল চলক $y$ প্রবর্তন করলে $F(x)$ কে এভাবে প্রকাশ করা যায়
$$F(x) = F(y) + (x-y)F'(y) + (x-y)^2 G(x,y),$$যেখানে $F'(x)$ হলো ডেরিভেটিভ ফর্মাল পাওয়ার সিরিজ যা এভাবে সংজ্ঞায়িত
$$F'(x) = \sum\limits_{i=0}^\infty (i+1)\alpha_{i+1}(x-\beta)^i,$$এবং $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$ বসিয়ে পাই
$$F(Q_{k+1}) \equiv F(Q_k) + (Q_{k+1} - Q_k) F'(Q_k) + (Q_{k+1} - Q_k)^2 G(x, y) \pmod x^{2a}.$$যেহেতু $Q_{k+1} - Q_k \equiv 0 \pmod{x^a}$, তাই $(Q_{k+1} - Q_k)^2 \equiv 0 \pmod{x^{2a}}$, সুতরাং
$$0 \equiv F(Q_{k+1}) \equiv F(Q_k) + (Q_{k+1} - Q_k) F'(Q_k) \pmod{x^{2a}}.$$শেষ সূত্রটি আমাদের $Q_{k+1}$ এর মান দেয়:
$$\boxed{Q_{k+1} = Q_k - \dfrac{F(Q_k)}{F'(Q_k)} \pmod{x^{2a}}}$$সুতরাং, পলিনোমিয়াল বিপরীতকরণ এবং $F(Q_k)$ গণনা জানলে, আমরা $P$ এর $n$ সহগ এই কমপ্লেক্সিটিতে খুঁজতে পারি
$$T(n) = T(n/2) + f(n),$$যেখানে $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$ ইত্যাদি মডুলোতে পূর্ণসংখ্যা ভাগশেষের ক্রম নিয়ে কাজ করি। উদাহরণস্বরূপ, নিউটনের পদ্ধতি একটি প্রদত্ত সংখ্যা ভিত্তিতে সব সম্ভব অটোমর্ফিক সংখ্যা (যে সংখ্যা বর্গ করলে নিজের মধ্যে শেষ হয়) খুঁজতে ব্যবহার করা যায়। সমস্যাটি পাঠকের জন্য অনুশীলন হিসেবে রেখে দেওয়া হলো। আপনার সমাধান $10$-ভিত্তিক সংখ্যার জন্য কাজ করে কিনা পরীক্ষা করতে এটি বিবেচনা করতে পারেন।
লগারিদম#
$\ln P(x)$ ফাংশনের জন্য জানা যে:
$$ \boxed{(\ln P(x))' = \dfrac{P'(x)}{P(x)}} $$সুতরাং আমরা $O(n \log n)$-এ $\ln P(x)$ এর $n$ সহগ গণনা করতে পারি।
বিপরীত সিরিজ#
দেখা যায়, নিউটনের পদ্ধতি ব্যবহার করে $A^{-1}$ এর সূত্র পাওয়া যায়। এর জন্য আমরা $A=Q^{-1}$ সমীকরণ নিই, সুতরাং:
$$F(Q) = Q^{-1} - A$$$$F'(Q) = -Q^{-2}$$$$\boxed{Q_{k+1} \equiv Q_k(2-AQ_k) \pmod{x^{2^{k+1}}}}$$সূচকীয়#
$e^{P(x)}=Q(x)$ গণনা শিখি। $\ln Q = P$ হওয়া উচিত, সুতরাং:
$$F(Q) = \ln Q - P$$$$F'(Q) = Q^{-1}$$$$\boxed{Q_{k+1} \equiv Q_k(1 + P - \ln Q_k) \pmod{x^{2^{k+1}}}}$$$k$-তম ঘাত#
এখন $P^k(x)=Q$ গণনা করতে হবে। এটি নিম্নলিখিত সূত্র দিয়ে করা যায়:
$$Q = \exp\left[k \ln P(x)\right]$$লক্ষ্য করুন, লগারিদম ও সূচকীয় সঠিকভাবে গণনা করতে পারবেন শুধু যদি কোনো প্রাথমিক $Q_0$ খুঁজে পান।
এটি খুঁজতে, পলিনোমিয়ালের ধ্রুবক সহগের লগারিদম বা সূচকীয় গণনা করতে হবে।
কিন্তু এটি করার একমাত্র যুক্তিসঙ্গত উপায় হলো $Q = \ln P$ এর জন্য $P(0)=1$ যেন $Q(0)=0$ এবং $Q = e^P$ এর জন্য $P(0)=0$ যেন $Q(0)=1$।
সুতরাং আপনি উপরের সূত্র শুধু $P(0) = 1$ হলেই ব্যবহার করতে পারেন। অন্যথায় যদি $P(x) = \alpha x^t T(x)$ যেখানে $T(0)=1$ তাহলে লেখা যায়:
$$\boxed{P^k(x) = \alpha^kx^{kt} \exp[k \ln T(x)]}$$লক্ষ্য করুন আপনি পলিনোমিয়ালের কোনো $k$-তম মূলও গণনা করতে পারেন যদি $\sqrt[k]{\alpha}$ গণনা করতে পারেন, উদাহরণস্বরূপ $\alpha=1$ এর জন্য।
মূল্যায়ন ও ইন্টারপোলেশন#
চার্প-z ট্রান্সফর্ম#
যে বিশেষ ক্ষেত্রে আপনাকে $x_r = z^{2r}$ বিন্দুতে পলিনোমিয়াল মূল্যায়ন করতে হবে সেখানে নিচের কাজ করা যায়:
$$A(z^{2r}) = \sum\limits_{k=0}^n a_k z^{2kr}$$$2kr = r^2+k^2-(r-k)^2$ প্রতিস্থাপন করি। তাহলে এই যোগফল এভাবে লেখা যায়:
$$\boxed{A(z^{2r}) = z^{r^2}\sum\limits_{k=0}^n (a_k z^{k^2}) z^{-(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}$। তাহলে
$$\boxed{A(z^r) = z^{-\binom{r}{2}}\sum\limits_{k=0}^n \left(a_k z^{-\binom{k}{2}}\right)z^{\binom{k+r}{2}}}$$$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$ পলিনোমিয়ালের গুণফলে $x^{n+r}$ এর সহগ $z^{\binom{r}{2}}A(z^r)$ এর সমান। $A_0(x)$ ও $A_1(x)$ এর সহগ গণনা করতে $z^{\binom{k+1}{2}}=z^{\binom{k}{2}+k}$ সূত্র ব্যবহার করা যায়।
বহুবিন্দু মূল্যায়ন#
ধরি আপনাকে $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})$ গণনা করবে, এখন $A(x) \pmod{P_{m,r}(x)}$ নিয়ে $[m,r)$ এর জন্যও একই করুন। ৪. প্রথম ও দ্বিতীয় রিকার্সিভ কলের ফলাফল জুড়ে রিটার্ন করুন।
পুরো প্রক্রিয়া $O(n \log^2 n)$-এ চলবে।
ইন্টারপোলেশন#
ল্যাগ্রাঞ্জের একটি সরাসরি সূত্র আছে পলিনোমিয়াল ইন্টারপোলেট করতে, $(x_i, y_i)$ জোড়ার সেট দেওয়া আছে:
$$\boxed{A(x) = \sum\limits_{i=1}^n y_i \prod\limits_{j \neq i}\dfrac{x-x_j}{x_i - x_j}}$$সরাসরি গণনা কঠিন কিন্তু দেখা যায়, বিভাজন ও জয় পদ্ধতিতে $O(n \log^2 n)$-এ গণনা করা যায়:
$P(x) = (x-x_1)\dots(x-x_n)$ বিবেচনা করুন। $A(x)$ এ হরের সহগ জানতে এরকম গুণফল গণনা করতে হবে:
$$ P_i = \prod\limits_{j \neq i} (x_i-x_j) $$কিন্তু ডেরিভেটিভ $P'(x)$ বিবেচনা করলে দেখা যাবে $P'(x_i) = P_i$। সুতরাং $O(n \log^2 n)$-এ মূল্যায়নের মাধ্যমে $P_i$ গণনা করা যায়।
এখন একই সেগমেন্ট ট্রিতে রিকার্সিভ অ্যালগরিদম বিবেচনা করুন যা বহুবিন্দু মূল্যায়নে ব্যবহৃত। এটি পাতায় প্রতিটি পাতায় $\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$ দিয়েও গুণ করতে পারি এবং পুরো গুণফল নিম্নলিখিত আকারে লেখা যায়:
$$\boxed{\mathcal{R}(A, B) = b_m^n\prod\limits_{j=0}^m A(\mu_j) = b_m^n a_m^n \prod\limits_{i=0}^n \prod\limits_{j=0}^m (\mu_j - \lambda_i)= (-1)^{mn}a_n^m \prod\limits_{i=0}^n B(\lambda_i)}$$উপরে সংজ্ঞায়িত মানটিকে পলিনোমিয়াল $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;
}
}হাফ-GCD অ্যালগরিদম#
$O(n \log^2 n)$-এ GCD ও রেজাল্ট্যান্ট গণনা করার একটি উপায় আছে।
এই প্রক্রিয়া একটি $2 \times 2$ রৈখিক রূপান্তর ইমপ্লিমেন্ট করে যা পলিনোমিয়ালের $(a(x), b(x))$ জোড়াকে আরেকটি $(c(x), d(x))$ জোড়ায় রূপান্তর করে যেন $\deg d(x) \leq \frac{\deg a(x)}{2}$। আপনি যথেষ্ট সাবধান হলে, অন্তত ২ গুণ ছোট পলিনোমিয়ালে সর্বোচ্চ ২টি রিকার্সিভ কল দিয়ে যেকোনো পলিনোমিয়াল জোড়ার হাফ-GCD গণনা করতে পারেন।
অ্যালগরিদমের নির্দিষ্ট বিবরণ ব্যাখ্যা করা কিছুটা ক্লান্তিকর, তবে আপনি লাইব্রেরিতে half_gcd ফাংশন হিসেবে এর ইমপ্লিমেন্টেশন পাবেন।
হাফ-GCD ইমপ্লিমেন্ট হলে, $\gcd(a, b)$ ও $0$ এর জোড়ায় সংকুচিত না হওয়া পর্যন্ত পুনরাবৃত্তিমূলকভাবে পলিনোমিয়ালে এটি প্রয়োগ করা যায়।