F

ধরি, $M = 10^7 + 19$.

সবার আগে ধরি, $g=6$ হচ্ছে $M$এর প্রিমিটিভ রুট। প্রিমিটিভ রুট বের করতে সময় লাগে $\mathcal{O}(\sqrt{M})$)। সুতরাং সংজ্ঞানুযায়ী, আমরা শূণ্য নয় এমন কোন সংখ্যাকে $g$ এর পাওয়ার এবং $M$এর মডুলো আকারে প্রকাশ করতে পারি। আবারো ধরি, $F_i \equiv g^{G_i} \pmod{M}$. লক্ষণীয় যে, একটি নির্দিষ্ট মড$M$এর জন্য, এমন কোন $k \le 10^6$ নাই যা $F_k \equiv 0 \, (\textrm{mod}\ M)$শর্তটি পূরণ করে। সুতরাং আমাদের ০ নিয়ে চিন্তা করতে হবে না। সকল $G_i$ যেখানে $0 < i < M$, কে $\mathcal{O}(M)$এ হিসাব করে বের করা যাবে।

এখন ধরি, $F_l^{F_r} \equiv g^{G_l \cdot F_r}\pmod M$।

তা হলে, আমাদের ইকুয়েশনটি দাঁড়ায়, $P(k) \equiv \prod\limits_{l \,=\, 1}^{n}{\prod\limits_{\substack{r \,=\, l,\\ MEX(l,\, r) \,=\, k}}^{n}{ g^{G_l \cdot F_r}}}\pmod M$
অথবা, $P(k) \equiv g^{\sum\limits_{l \,=\, 1}^{n}{\sum\limits_{\substack{r \,=\, l,\\ MEX(l,\, r) \,=\, k}}^{n}{G_l \cdot F_r}}} \pmod M$

সুতরাং, আমাদেরকে এই ${G_l \cdot F_r}$গুণফলগুলোর যোগফল নির্ণয় করতে হবে।

ধরি, $ans_k = \sum\limits_{i = k}^{n}{P(k)}$। তা হলে আমরা ০ থেকে $n$এর মধ্যে সবগুলো $k$ এর জন্য $ans_k$ এর মান বের করবো।

এখন $left$ অ্যারেটি বানাতে হবে যেখানে, $left_r$ $r$ থেকে ছোট বা সমান রেঞ্জের সর্বোচ্চ ইনডেক্স যার প্রতিটা ইনডেক্স $l \le left_r$এর জন্য $[l, r]$ পর্যন্ত সাব-অ্যারের MEX অবশ্যই $\ge k$হবে। MEX হচ্ছে সর্বনিম্ন অৠণাত্মক সংখ্যা যা এই সাব-অ্যারেতে অনুপস্থিত।

এখন আমরা $০$ থেকে $n$ এর মধ্যে সকল $k$ এর জন্য $left$ অ্যারেটি বের করি। $k + ১$ এর জন্য অ্যারেটি বানানোর জন্য আমরা $a$ তে $k$ এর উপস্থিতি থাকলে সেটা দিয়ে $left$ কে আপডেট করবো। এটার জন্য আমাদেরকে নিম্নবর্ণিত কাজ দুটি করতে হবে:

• রেঞ্জ আপডেট যেমন $(L, R)$ রেঞ্জ এবং ইন্টিজার $x$ এর জন্য: $left_i = \min(left_i, x): L\le i \le R$

• রেঞ্জ আপডেট যেমন: $F_i \cdot (G_1 + G_2 + \dots + G_{left_i}): 1 \le i \le n$এর যোগফল।

আমরা এই অংশটুকু সেগমেন্ট ট্রি বিটসের সাহায্যে সমাধান করতে পারি। এই ব্যাপারে আরো জানতে সেটারের সলিউশন দেখুন।

এখানে আরো লক্ষ্যণীয় যে$left$ একটি নন-ডিক্রিসিং অ্যারে। সুতরাং সাধারণ সেগমেন্ট ট্রি দিয়েও অপারেশনটি করা যায়।

সামগ্রিক কমপ্লেক্সিটি: $\mathcal{O}(n \, log(n) + M)$.

সেটারের সলিউশনের জন্য: এখানে ক্লিক করুন ।