Inversion Invasion

1. GCD classes

Let $C_d = \{v \in [1,n] \mid \gcd(v,n)=d\},$ where $d$ is a divisor of $n$.

A position with $a_i=d$ must receive a value from $C_d$. A free position ($a_i=0$) can receive anything leftover.

The size of class $C_d$ is $|C_d| = \varphi\!\left(\frac{n}{d}\right),$ because every $v \in C_d$ can be written as $v=d\cdot t, \qquad 1\le t\le \frac nd, \qquad \gcd\left(t,\frac nd\right)=1.$

Let $m_d$ be the number of currently constrained positions requiring class $d$. Then valid permutations exist iff $m_d \le |C_d| \quad \text{for all } d\mid n.$

No magic here: if some class is overbooked, you're cooked.

---

2. Counting valid permutations

Suppose the current state is valid. Let $k=\sum_d m_d, \qquad f=n-k$ be the number of constrained and free positions.

For each divisor $d$:

• choose and order $m_d$ distinct values from $C_d$ for the constrained positions of type $d$,
• then place all remaining $f$ values arbitrarily on the free positions.

So the number of valid permutations is $W = f! \prod_d \frac{|C_d|!}{(|C_d|-m_d)!}.$

This formula is exactly what we need, because after adding one new constraint $(i,x)$, only one class changes and $f$ decreases by $1$.

If before the query the class $x$ had $m_x$ constrained positions, then $W' = W \cdot \frac{|C_x|-m_x}{n-k}.$

That is a sweet $O(1)$ update.

If $|C_x|-m_x=0$, then $W'=0$, and from now on the answer is forever $0$. No resurrection arc here.

---

3. The real aha: only the value $n$ matters

Now for the inversion sum. Doing it class-by-class looks tempting, and also like a great way to waste your afternoon.

Define the involution on values:

n-v,& v<n,\\ n,& v=n. \end{cases}$$ For every $v<n$, $$\gcd(T(v),n)=\gcd(n-v,n)=\gcd(v,n),$$ so if a value $v<n$ is allowed at some constrained position, then $n-v$ is allowed there too. Also, if a position requires $a_i=n$, the only possible value is $n$, and $T(n)=n$, so that is preserved as well. Therefore, applying $T$ to every value of a valid permutation gives **another valid permutation**. Now look at any two values $u,v<n$. Their order flips: $$u>v \iff n-u < n-v.$$ So for every valid permutation where this pair forms an inversion, there is another valid permutation where it does not. ### Consequence Every pair of values not involving $n$ contributes inversions in exactly half of all valid permutations. There are $n-1$ values different from $n$, so the total contribution of all such pairs is $$W \cdot \frac{\binom{n-1}{2}}{2}.$$ That leaves exactly one troublemaker: the value $n$. --- ## 4. Contribution of the value $n$ Since $n$ is the largest value, if it is placed at position $p$, it contributes exactly $$n-p$$ inversions: one with every later position. So we only need to know where $n$ can be. ### Case 1: some query used $x=n$ Then that position must contain value $n$. There is only one such value, since $$|C_n|=\varphi(1)=1.$$ Let its position be $p_n$. Then every valid permutation has the same contribution from $n$: $$n-p_n.$$ So $$\text{InvSum} = W \left( \frac{\binom{n-1}{2}}{2} + (n-p_n) \right).$$ ### Case 2: no query used $x=n$ Then value $n$ is among the leftover values, hence it is placed on a **free** position. Among all valid permutations, all $f$ free positions are symmetric, so $n$ is uniformly distributed over them. Therefore its expected contribution is the average of $n-i$ over free positions $i$: $$\frac{1}{f}\sum_{i\in \text{free}} (n-i).$$ Let $$S = \sum_{i\in \text{constrained}} i.$$ Then $$\sum_{i=1}^n (n-i)=\frac{n(n-1)}{2},$$ and $$\sum_{i\in \text{free}} (n-i) = \frac{n(n-1)}{2} - \sum_{i\in \text{constrained}} (n-i) = \frac{n(n-1)}{2} - kn + S.

So in this case $\text{InvSum} = W \left( \frac{\binom{n-1}{2}}{2} + \frac{\frac{n(n-1)}{2} - kn + S}{f} \right).$

That’s it. Seriously. The entire inversion structure collapses to tracking the location of the largest value. Pretty funny, honestly.

---

5. What to maintain per test case

We process queries online and maintain:

• $m_x$ for queried divisors $x$,
• $k$ = number of constrained positions,
• $S$ = sum of constrained indices,
• $W$ = number of valid permutations modulo $998244353$,
• whether value $n$ is already forced, and if yes, its position $p_n$.

For a query $(i,x)$:

1. Update $W \leftarrow W \cdot \frac{\varphi(n/x)-m_x}{n-k}.$
2. Increment $m_x$, $k$, and $S$.
3. If $x=n$, remember $p_n=i$.
4. If the state became invalid, print $0$ forever after.
5. Otherwise compute the formula from the previous section.

All divisions are modulo $998244353$, and this is safe because $n \le 2\cdot 10^6 < 998244353$.

---

6. Complexity

We precompute:

• Euler phi for all numbers up to $2\cdot 10^6$,
• factorials and modular inverses up to $2\cdot 10^6$.

That costs $O(N_{\max}\log\log N_{\max})$ for phi (or linear if you prefer), and $O(N_{\max})$ for factorials/inverses.

Each query is then processed in $O(1).$

So the total complexity is O\!\left(N_{\max}\log\log N_{\max} + \sum q\right), with memory $O(N_{\max}).$

Very fast, very clean, no cursed data structures required.