Hints: Amanojaku and Sequence (Tutorial Version)

Warmup (read this first, without E0). You are given $n$ and $m$. Consider every sequence $c=(c_1,\ldots,c_n)$ with $c_i \ge 0$ and $c_1+\cdots+c_n=m$. For each $c$, let $P_i=c_1+\cdots+c_i$ and $f(c)=\sum_{i=1}^n P_i^2$. Define $G(n,m)$ as the sum of $f(c)$ over all such $c$, modulo $998244353$.

For $n=1$, $m=2$, what is the only $c$? What is $G(1,2)$?

Answer to Hint 1: The only sequence is $c=[2]$. Prefixes: $P_1=2$. So $G(1,2)=2^2=4$.

In general, valid $c$ are exactly compositions of $m$ into $n$ non-negative parts. There are $\binom{m+n-1}{n-1}$ of them when $n \ge 1$.

Still in the warmup: $n=2$, $m=5$. List all pairs $(c_1,c_2)$ with $c_1+c_2=5$, write $(P_1,P_2)$ and $f(c)=P_1^2+P_2^2$. What is $G(2,5)$?

Answer to Hint 3: The six pairs are $(0,5),(1,4),(2,3),(3,2),(4,1),(5,0)$ with $f$ values $25,26,29,34,41,50$. So $G(2,5)=205$.

For $n=4$, $m=7$, brute force is heavier but the same idea gives $G(4,7)=12180$. That number will reappear in E0 when every entry is $-1$.

We want $G(n,m)=\sum_c f(c)$ without enumerating every $c$. Fix $i$. Does the prefix $P_i$ depend on $c_{i+1},\ldots,c_n$, or only on $c_1,\ldots,c_i$?

Answer to Hint 5: $P_i$ uses only the first $i$ entries. So process $i=1,2,\ldots,n$ left to right: as soon as you choose $c_i$, the term $P_i^2$ in $f(c)$ is fixed for that partial assignment.

After filling the first $i-1$ entries, suppose their sum is $s$. Among all partial sequences with that sum $s$, what four numbers would let you add the next value $c_i=v$ in bulk (without looping over each partial $c$ one by one)?

Answer to Hint 7: For each $s \in [0,m]$, store:

• $\mathrm{cnt}[s]$ — how many partial assignments have sum $s$;
• $\mathrm{pref}[s]$ — sum of current prefix $P_{i-1}$;
• $\mathrm{pref2}[s]$ — sum of $P_{i-1}^2$;
• $\mathrm{sq}[s]$ — sum of $\sum_{j

Start: $\mathrm{cnt}[0]=1$, rest $0$. To add $c_i=v$, go $s \to s+v$ and use

$$\mathrm{sq}[s+v] \mathrel{+}= \mathrm{sq}[s] + \mathrm{pref2}[s] + 2v\,\mathrm{pref}[s] + \mathrm{cnt}[s]\,v^2$$

(and update $\mathrm{cnt}$, $\mathrm{pref}$, $\mathrm{pref2}$ the same way as in the editorial). After $n$ free positions, $G(n,m)=\mathrm{sq}[m]$.

Now return to the full problem. Array $b$ has $b_i \ge 0$ (forced $c_i=b_i$) or $b_i=-1$ (free $c_i \ge 0$), and $\sum_i c_i=m$. Let $F=\sum_{b_i\ge 0} b_i$ and $R=m-F$. When is $g(b,m)=0$? If every $b_i=-1$, how does $g(b,m)$ relate to $G(n,m)$ from the warmup?

Answer to Hint 9: If $R<0$, fixed values already exceed $m$, so no valid $c$ and the answer is $0$.

If all $b_i=-1$, there are no fixed entries: $F=0$, $R=m$, and $g(b,m)=G(n,m)$ — the warmup DP is the whole answer.

Run the same four-table DP on $s=0,\ldots,R$ (total already placed on free slots). You scan $b$ left to right. What changes when the current entry is fixed $b_i=v \ge 0$ instead of free?

Answer to Hint 11: Fixed $v$: every assignment at sum $s$ has its prefix increased by $v$, but $s$ stays the same. Add

$$\mathrm{pref2}[s] + 2v\,\mathrm{pref}[s] + \mathrm{cnt}[s]\,v^2$$

to $\mathrm{sq}[s]$, then update $\mathrm{pref}[s]$ and $\mathrm{pref2}[s]$ as in Hint 8 with the same $(p+v)^2$ expansion (no loop over $v$, no change of $s$).

When $b_i=-1$, the transition is exactly the warmup step from Hint 8, but with total budget $R$ instead of $m$. After processing all of $b$, which table entry is $g(b,m)$?

Answer to Hint 13: Free step: for each $s$, each $v \ge 0$ with $s+v \le R$, merge into $s+v$ using the same four formulas as in Hint 8.

Final answer: $g(b,m)=\mathrm{sq}[R]$ (mod $998244353$), provided $R \ge 0$.

Check: $b=[6,-1]$, $m=8$ gives $F=6$, $R=2$, answer $100$. $b=[-1,-1,3,-1]$, $m=5$ gives $F=3$, $R=2$, answer $286$.

E1 asks for the same $g$ on a subarray; E0 on the full array is “warmup DP + fixed steps,” and E1 adds range structure on top.