Editorial for F

Let M=107+19M = 10^7 + 19.

First things first, let g=6g=6 be the primitive root of MM(Primitive roots can be calculated in O(M)\mathcal{O}(\sqrt{M})). So by definition, we can express any number 0\neq 0 using some power of gg under modulo MM. Let, FigGi(modM)F_i \equiv g^{G_i} \pmod{M}. Notice that, for the given mod, MM, there is no such value k106k \le 10^6 s.t. Fk0(mod M)F_k \equiv 0 \, (\textrm{mod}\ M). So we don't have to worry about dealing with zeroes. All GiG_i for 0<i<M0 < i < M can be calculated in O(M)\mathcal{O}(M).

Now, FlFrgGlFr(modM)F_l^{F_r} \equiv g^{G_l \cdot F_r}\pmod M.

So our equation becomes P(k)l=1nr=l,MEX(l,r)=kngGlFr(modM)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

or, P(k)gl=1nr=l,MEX(l,r)=knGlFr(modM)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

So we have to compute the sum of the products GlFr{G_l \cdot F_r}.

Let ansk=i=knP(k)ans_k = \sum\limits_{i = k}^{n}{P(k)}. We will compute anskans_k for each kk from 00 to nn.

Build an array leftleft where leftrleft_r is the maximum index r\leq r such that for each index lleftrl \le left_r, MEX of the subarray [l,r][l, r] is k\ge k.

Now, let's build the array leftleft for each kk from 00 to nn in order. To generate the array for k+1k + 1, update the array leftleft using the occurrences of kk in aa. For that we have to perform:

  • range updates like set lefti=min(lefti,x):LiRleft_i = \min(left_i, x): L\le i \le R for some range (L,R)(L, R) and some integer xx.

  • range queries like sum of Fi(G1+G2++Glefti):1inF_i \cdot (G_1 + G_2 + \dots + G_{left_i}): 1 \le i \le n.

We can solve this part using Segment Tree Beats. Please see the setter’s solution for more clarity.

One can also observe that leftleft is a non-decreasing array. So the operations can also be done using a normal segment tree.

Overall Complexity: O(nlog(n)+M)\mathcal{O}(n \, log(n) + M).

Setters solution: smash here .


    83% Solution Ratio

    Um_nikEarliest, 3M ago

    user.794723Fastest, 1.0s

    Um_nikLightest, 117 MB

    Deshi_TouristShortest, 4088B

    Toph uses cookies. By continuing you agree to our Cookie Policy.