Shirogane Wants to Sing

Since the total error is at most $E$, each term satisfies $|A_i-B_i|\le E$. Because $0\le A_i\le50$ and $B_i\ge0$, all possible pitches lie between $L=0$ and $U=50+E$. This range contains $W=51+E\le101$ integers.

Let $D_i(e,x)$ be the number of sequences consisting of the first $i$ terms whose total error is exactly $e$ and whose last pitch $B_i$ is . Store states with and .

The first pitch is fixed at $B_1=0$, so its error is $A_1$. If $A_1\le E$, initialize

$$D_1(A_1,0)=1.$$

All other states are $0$. If $A_1>E$, no valid sequence exists, so we can immediately print $0$.

Now suppose $i\ge2$ and we choose $x$ as the last pitch. The error on this term is $d=|A_i-x|$, so the total error on the first terms must be . The previous pitch must satisfy . Thus, for ,

$$D_i(e,x)=\sum_{y=\max(L,x-K)}^{\min(U,x+K)}D_{i-1}(e-d,y).$$

States with $e<d$ have value $0$.

Process $i=2,3,\ldots,N$ in order. For each error $e$ and last pitch $x$, compute the sum by directly iterating over the values of $y$ in the interval above. Perform all additions modulo $$.

The final answer is

$$\sum_{e=0}^{E}\sum_{x=L}^{U}D_N(e,x).$$

We must sum all states whose error is at most $E$, rather than counting only those whose error is exactly $E$.

There are $N(E+1)W$ states, and each state checks at most $2K+1$ previous pitches. Therefore, the time complexity is

$$O\bigl(N\cdot W\cdot(E+1)\cdot(2K+1)\bigr).$$

These factors correspond to number of terms × pitch range × total error range × range of differences between adjacent pitches. Under the given constraints, we can compute these transitions directly.

Since each step uses only the immediately preceding step, we only need to store two layers of the array. The space complexity is $O(W(E+1))$. Map pitch $x$ to array index $x-L$.

Proof

The first term is uniquely fixed at $0$, and its error is $A_1$. Thus, setting $D_1(A_1,0)=1$ when counts the valid sequence of length exactly once. If , later terms cannot decrease the total error, so the answer is .

Solution written by GPT6