Growth Factor

Sources checked: the official Codeforces statement and the official tutorial PDF. I did not find a useful public accepted-source mirror quickly, so the implementation below is derived from the official approach and verified against the canonical statement/samples.

First kill the annoying part of the constraints.

Since $b_i \mid b_{i+1}$ and all values are positive, we always have $b_i \le b_{i+1}$. So if a value is used at position $i$, it must also be no larger than every later upper bound. Therefore we may replace

$$a_i \leftarrow \min_{j\ge i} a_j.$$

This is exact: every original valid sequence satisfies the tightened bound, and every sequence satisfying the tightened bound obviously satisfies the original bound. After this, $a$ is nondecreasing. Let $M=a_n$, and for each value $v\le M$, define

$$\operatorname{left}(v)=\min\{i:a_i\ge v\}.$$

So value $v$ is allowed exactly at positions $\operatorname{left}(v),\operatorname{left}(v)+1,\ldots,n$.

Define $f_v(l)$ as the number of valid prefixes $(b_1,\ldots,b_l)$ ending with $b_l=v$.

A valid prefix ending in $v$ has one of two forms:

• it is entirely $v,v,\ldots,v$, possible only when $v\le a_1$;
• otherwise, the last strict value change is from some proper divisor $u\mid v$, $u<v$, at an index $j$: the prefix of length $j$ ends at $u$, and positions $j+1,\ldots,l$ are all $v$.

For the transition $u\to v$ to be legal, we need $j\ge 1$, $u$ allowed at position $j$, and $v$ allowed at position $j+1$. So define

$$L(u,v)=\max\left(1,\operatorname{left}(u),\operatorname{left}(v)-1\right).$$

Then for $l\ge \operatorname{left}(v)$,

$$f_v(l)=[v\le a_1]+\sum_{\substack{u\mid v\\u<v}}\sum_{j=L(u,v)}^{l-1} f_u(j).$$

Doing this directly is dead on arrival: too many positions, too many sums.

The trick is to store each $f_v(l)$ in the binomial basis:

$$f_v(l)=\sum_{k\ge 0}D_v[k]\binom{l}{k}\quad(l\ge \operatorname{left}(v)),$$

and $f_v(l)=0$ before $v$ is allowed.

Why this basis? Because of the hockey-stick identity:

$$\sum_{j=L}^{l-1}\binom{j}{k}=\binom{l}{k+1}-\binom{L}{k+1}.$$

Since $L(u,v)$ includes $\operatorname{left}(u)$, the polynomial form for $f_u(j)$ is valid throughout the summed range. So if $f_u(j)$ contains the term $D_u[k]\binom{j}{k}$, then its contribution to $f_v(l)$ is

$$D_u[k]\binom{l}{k+1}-D_u[k]\binom{L(u,v)}{k+1}.$$

That means a transition from $u$ to $v$ does exactly this:

$$D_v[k+1] \mathrel{+}= D_u[k],$$ $$D_v[0] \mathrel{-}= D_u[k]\binom{L(u,v)}{k+1}.$$

Also, if $v\le a_1$, add $1$ to $D_v[0]$ for the all-$v$ sequence.

Process values $u=1,2,\ldots,M$. By the time we process $u$, all its proper-divisor contributions are already done, because every proper divisor is smaller. Then propagate from $u$ to every multiple $v=2u,3u,\ldots$.

The number of useful coefficients is tiny. Every strict transition replaces a value by a proper multiple, so the value at least doubles. Thus a chain has at most $\lfloor\log_2 M\rfloor$ strict transitions. With $M\le 200000$, storing about 20 coefficients is plenty. That’s the whole 2900-rated punchline: the DP looks huge, but the degree is capped by growth. Cute, and mildly evil.

Finally, every value $v\le M$ is allowed at position $n$, so the answer is

$$\sum_{v=1}^{M} f_v(n)=\sum_{v=1}^{M}\sum_k D_v[k]\binom{n}{k}.$$

Edge cases:

• If $n=1$, there are exactly $a_1$ choices. The DP also gives this.
• If $M=1$, only the all-ones sequence exists.
• Empty transition sums are handled correctly because $\binom{l}{k+1}-\binom{L}{k+1}=0$ when $L=l$.
• All arithmetic is modulo $998244353$.

Complexity:

There are $\sum_{u=1}^M O(M/u)=O(M\log M)$ divisor-to-multiple pairs, and $O(\log M)$ coefficients per pair. So the total time is

$$O(n\log M+M\log^2 M),$$

with small constants. Memory is $O(M\log M).$