Editorial: Amanojaku and Sequence (Tutorial Version)

We build the solution in two layers: a warmup where every position is free, then the full E0 problem with fixed and free entries. The warmup is stated on its own so you can master the DP before seeing $-1$ mixed with fixed values.

Given integers $n \ge 1$ and $m \ge 0$, consider all sequences

with $c_i \in \mathbb{Z}_{\ge 0}$ and $c_1 + \cdots + c_n = m$.

For each such $c$, define prefix sums $P_i = c_1 + \cdots + c_i$ and

Compute

There is no array $b$ and no $-1$ in this warmup — only $n$, $m$, and the sum over all non-negative compositions of $m$ into $n$ parts.

Tiny examples

• $G(1,2)$: only $c=[2]$, prefixes $2$, so $G(1,2)=4$.
• $G(2,5)$: all pairs with $c_1+c_2=5$:

Sum $= 205$, so $G(2,5)=205$.

• $G(4,7)=12180$ (all $12180$ compositions with four non-negative parts summing to $7$; brute force is fine for checking).

By stars and bars there are $\binom{m+n-1}{n-1}$ compositions when $n \ge 1$. For $n=2$, $m=5$ that is $\binom{6}{1}=6$, matching the table.

We cannot afford to list them when $m$ is large, but we can process positions $1,\ldots,n$ one at a time and aggregate contributions.

When building $c$ from left to right, after fixing $c_1,\ldots,c_{i-1}$:

• the prefix $P_{i-1}$ is already known;
• the term $P_i^2$ for the next index depends only on the choice $c_i$;
• later choices only shift future prefixes by the same amount.

So we keep bulk statistics over all partial assignments instead of storing each $c$.

After processing the first $i-1$ positions, for each total $s = c_1+\cdots+c_{i-1}$ ($0 \le s \le m$), store:

Start: $\mathrm{cnt}[0]=1$, other entries $0$ (empty prefix $P_0=0$).

After all $n$ positions: every full $c$ has total $m$, so

Choose $c_i = v \ge 0$ and move $s \to s+v$. Every old partial assignment with mass $c=\mathrm{cnt}[s]$, prefix sum $p$, and accumulated $\mathrm{sq}[s]$ contributes:

• new prefix $p+v$, so add $(p+v)^2$ to $f$;
• bulk sum of $(p+v)^2$ over those assignments:

Transitions for each $s$ and each $v$ with $s+v \le m$:

This is the entire warmup algorithm: repeat for $i=1,\ldots,n$, then output $\mathrm{sq}[m]$.

Before any position: $\mathrm{cnt}[0]=1$, $\mathrm{pref}[0]=\mathrm{pref2}[0]=\mathrm{sq}[0]=0$.

Position 1 (choose $v=c_1$):

After position $1$, state $s$ has $\mathrm{sq}[s]=s^2$ (only one prefix so far).

Position 2 (choose $c_2$ so $s+v=5$):

From $s=0$, $v=5$: one assignment $[0,5]$, contributes $0^2+5^2=25$ to $\mathrm{sq}[5]$.

From $s=1$, $v=4$: one assignment $[1,4]$, prefixes $1,5$, contributes $1+25=26$.

Summing all splits gives $\mathrm{sq}[5]=205=G(2,5)$.

Run the same DP; the answer is $G(4,7)=12180$. This matches sample case “four -1s, $m=7$” in E0 — because when every $b_i=-1$, the full problem is exactly $G(n,m)$.

Now let $b=(b_1,\ldots,b_n)$ with $b_i \ge -1$. A sequence $c$ is valid for $(b,m)$ if:

• $|c|=n$ and $\sum_i c_i = m$;
• if $b_i \ge 0$, then $c_i = b_i$;
• if $b_i = -1$, then $c_i \ge 0$ is arbitrary.

Define $f(c)$ as before and $g(b,m)=\sum_{\text{valid }c} f(c)$, or $0$ if no valid $c$ exists.

Link to warmup: if $b_i=-1$ for all $i$, then $g(b,m)=G(n,m)$.

Let

Fixed slots must contribute $F$; free slots must contribute $R$ in total. If $R<0$, then $g(b,m)=0$.

If there are no free slots ($k=0$), there is at most one $c$; check $R=0$ and evaluate $f(c)$ directly.

Otherwise run the same four-table DP on $s=0,\ldots,R$, but only over free totals $s$ (the amount already placed on -1 positions seen so far).

Fixed $b_i = v \ge 0$: every assignment at sum $s$ adds $v$ to its prefix. Same algebra as choosing a fixed $v$ in the warmup, but $s$ does not change:

(use old $\mathrm{pref}[s]$ in the $\mathrm{pref2}$ line, as in code).

Free $b_i=-1$: identical to the warmup transition with budget $R$ instead of $m$.

Answer: $\mathrm{sq}[R]$ modulo $998244353$.

$F=6$, $R=2$. After fixed $6$: $\mathrm{cnt}[0]=1$, $\mathrm{pref}[0]=6$, $\mathrm{pref2}[0]=36$, $\mathrm{sq}[0]=36$.

Free slot: $v=0$ leaves $[6,6]$; $v=2$ gives $[6,2]$ with $f=36+64=100$. So $g=100$.

$F=3$, $R=2$. Fixed $3$ at index $3$ forces that prefix; the three free slots split total $2$. DP yields $286$.

Let $R=m-F$. Each free index costs $O(R^2)$ in the straightforward loop over $v$; each fixed index costs $O(R)$. E0 limits ($n \le 100$, $m \le 500$, $\sum n\cdot m \le 5\cdot 10^5$) are sized for this.

• Warmup ($n$ free): learn $G(n,m)=\mathrm{sq}[m]$ and the four aggregates.
• E0: same DP with fixed steps and answer $\mathrm{sq}[R]$.
• E1 / E2: subarray queries and updates on top of the same combinatorial core.

See model_sol.cpp for the implementation (AtCoder modint998244353).