If you keep getting WA at problem A, maybe you can try this case

n = 4, and a[4] = {2, 1, 2, 2}

the answer should be 1.

tasks were somewhat standard today. Particularly, A and D.

A, to me, was just straightforward implementation. D was trivial extension of 1967E1 - Again Counting Arrays (Easy Version).

B was nice! Thanks for the ratings anyways.

Can someone help with any hints/intuition for C?

I was expecting worse from the problem D with its 15s TL, but my solution ($$$T^{3/2}$$$ or something) works in ~800ms.

Also, I had a revelation that counting 1-d walks with not moving sometimes can be computed from 1-d walks with always moving via a simple convolution (and the always-moving part here was doable in like $$$T^2/H$$$).

Anyway, thanks for the contest!

In Editorial for C, I am assuming we calculate each $$$F_i$$$ as follows:

$$$F_i = \frac{R_i}{ \prod_{d \mid i, d \neq i} F_d}$$$ and base case $$$F_1 = 1$$$

So how do we prove that $$$F_1,F_2...F_n$$$ are all integers and are pairwise coprime?

Loved the problems! B is very nice!

My solution to C is $$$O(\sum_{i=1}^Md^2(i))=O(M \log M \sqrt M)$$$,where $$$d(i)$$$ is the number of factors of $$$i$$$, but it still pass.(The judge in atcoder is really fast.)

My submission

Can somebody explain the discussion of situation $$$W$$$ is even in problem B? I can only find out the conclusion when $$$W$$$ is odd.

Different explanation of C, though the point should be the same: we start by calculating just the last answer since the resulting algorithm can be implemented in an online queries way.

Using the standard subtraction formula for GCD, we derive $$$GCD(10^a-1, 10^b-1) = 10^{GCD(a,b)}-1$$$. This generalises to an arbitrary number of elements.

We know $$$max(S) = \sum_{T \subset S, T \neq \emptyset} (-1)^{|S|+1} min(T)$$$, e.g. max(a,b,c,d) = a+b+c+d-min(a,b)-min(a,c)-...-min(c,d)+min(b,c,d)+min(a,c,d)+min(a,b,d)+min(a,b,c)-min(a,b,c,d). Simple proof: the $$$k$$$-th largest element will appear in $$$2^{k-1}$$$ sets, their parities cancel out iff $$$k \gt 1$$$. Since the exponents of all primes in LCM are max over those in $$$A_i$$$ and exponents of all primes in GCD are min, the same rule works if max/min are replaced with LCM/GCD and add/sub with mul/div.

Among the exponents $$$A_i$$$, we need to calculate the (count of odd-sized subsets — count of even-sized subsets) "count-dif" with each possible GCD; then the answer is $$$\prod_i (10^i-1)^{cnt_{i,odd} - cnt_{i,even}}$$$. First we calculate the count of exponents divisible by each $$$i$$$. If there are none, $$$i$$$ can be ignored. Otherwise the count-dif of subsets whose GCD is divisible by $$$i$$$ is exactly 1 because it'd be 0 if we included the empty subset (GCD = 0) and that has even size. From that, we need to subtract the count-dif of all proper multiples of $$$i$$$ to get count-dif of subsets whose GCD is equal to $$$i$$$. This can be calculated in the decreasing order of $$$i$$$, in $$$O(M \log M)$$$.

How do we generalise this to online queries? The key is that the exact count of exponents divisible by $$$i$$$ doesn't matter, the only thing that affects the answer is if it's non-zero. When a new $$$A_i$$$ comes in, we update that for $$$A_i$$$ and recursively for all its minimal divisors (from $$$a$$$ to $$$a$$$ / prime), immediately turning back in recursion if some $$$a$$$ already occurred before. This ensures that each divisor is only processed once so recursion tries to branch $$$O(M \log M)$$$ times.

The second thing is that going from count-dif for GCD divisible by $$$i$$$ to count-dif for GCD equal to $$$i$$$ is a linear operation, so each operation "$$$i$$$ appeared for the first time as a divisor" just multiplies the answer by some $$$c_i$$$. These $$$c_i$$$ can be calculated in the exact same way we calculated count-dif, just in increasing order: $$$c_i = (10^i-1) / \prod_{d | i} c_d$$$.