Official Analysis (C++)

Explanation

Let $a_i$ be Bessie's ith instruction and $b_j$ be Elsie's jth instruction. Additionally, let $I(i, j)$ denote the set of unique expressions we can make by interleaving Bessie's first $i$ instructions and Elsie's first $j$ instructions. For example, in the sample:

3
12+
+02

• $I(0, 0)$: $\{0\}$ (interleaving $[\ ]$ and $[\ ]$)
• $I(0, 1)$: $\{+y\}$ (interleaving $[\ ]$ and $[+y]$)
• $I(2, 1)$: $\{+y, +2y\}$ (interleaving $[*1, *2]$ and $[+y]$)
• $I(3, 3)$: $\{0, +x, +2x\}$ (interleaving $[*1, *2, +x]$ and $[+y, *0, *2]$)

So, how do we calculate $|I(i, j)|$?

When either $i$ or $j$ are 0, either Bessie or Elsie's instruction set will be empty, meaning the interleaving is uniquely determined and thus $\boxed{|I(i, 0)| = |I(0, i)| = 1}$ for all $i \leq N$.

Great, but what if $i$ and $j$ are both nonzero? Evidently, any interleaving of Bessie's first $i$ instructions and Elsie's first $j$ instructions must either end with instruction $a_i$ or instruction $b_j$. We can thus rewrite the expressions that end with $a_i$ as $I(i - 1, j) \rightarrow a_i$ (let's denote this set as $A$) and the ones that end with $b_j$ as $I(i, j - 1) \rightarrow b_j$ (let's denote this set as $B$). We also have the following:

1. As long as $a_i$ isn't $*0$, $\boxed{|A| = |I(i - 1, j)|}$
2. As long as $b_j$ isn't $*0$, $\boxed{|B| = |I(i, j - 1)|}$
3. $I(i, j) = A \cup B$

Take some time to convince yourself of these, especially points 1 and 2!

At this point, you may be tempted to conclude that

Don't make this mistake! Remember the Principle of Inclusion-Exclusion:

For example, if $S = \{1, 2\}$ and $T = \{2, 3\}$, we overcount $2$ if we simply concatenate these two sets, so we need to subtract $|S \cap T|$, which, in this case, is $|\{2\}| = 1$.

In our case, we overcount $|A \cap B|$. So which expressions are in this set? This is a crucial part of the solution, so make sure to spend some time thinking about it before reading the answer below! To make this easier, you may want to first assume neither Bessie nor Elsie has the $*0$ instruction, as it's not too hard to figure out whether $I(i, j)$ contains the $0$ expression and reduces the number of edge cases we need to consider.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2e3 + 1;
const int MOD = 1e9 + 7;

// adding and subtracing under mod
ll ad(ll &a, ll b) { return a = (a + b) % MOD; }