Pair Programming

Explicación

Sea $a_i$ la $i$ -ésima instrucción de Bessie y $b_j$ la $j$ -ésima instrucción de Elsie. Además, sea $I(i, j)$ el conjunto de expresiones únicas que podemos formar intercalando las primeras $i$ instrucciones de Bessie y las primeras $j$ instrucciones de Elsie. Por ejemplo, en el sample:


3
12+
+02

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

Entonces, ¿cómo calculamos $|I(i, j)|$ ?

Cuando $i$ o $j$ son 0, el conjunto de instrucciones de Bessie o el de Elsie estará vacío, lo que significa que el intercalado está unívocamente determinado y por lo tanto $\boxed{|I(i, 0)| = |I(0, i)| = 1}$ para todo $i \leq N$ .

Bien, ¿pero qué pasa si $i$ y $j$ son ambos distintos de cero? Evidentemente, cualquier intercalado de las primeras $i$ instrucciones de Bessie y las primeras $j$ de Elsie debe terminar o bien con la instrucción $a_i$ o bien con la instrucción $b_j$ . Así podemos reescribir las expresiones que terminan con $a_i$ como $I(i - 1, j) \rightarrow a_i$ (denotemos este conjunto como $A$ ) y las que terminan con $b_j$ como $I(i, j - 1) \rightarrow b_j$ (denotemos este conjunto como $B$ ). También tenemos lo siguiente:

Mientras $a_i$ no sea $*0$ , $\boxed{|A| = |I(i - 1, j)|}$
Mientras $b_j$ no sea $*0$ , $\boxed{|B| = |I(i, j - 1)|}$
$I(i, j) = A \cup B$

¡Tómese un tiempo para convencerse de esto, especialmente de los puntos 1 y 2!

En este punto, uno puede verse tentado a concluir que

|I(i, j)| = |A \cup B| = |A| + |B| = |I(i - 1, j)| + |I(i, j - 1)|

¡No cometamos este error! Recordemos el principio de inclusión-exclusión:

|S \cup T| = |S| + |T| - |S \cap T|

Por ejemplo, si $S = \{1, 2\}$ y $T = \{2, 3\}$ , sobrecontamos $2$ si simplemente concatenamos estos dos conjuntos, así que hay que restar $|S \cap T|$ , que en este caso es $|\{2\}| = 1$ .

En nuestro caso, sobrecontamos $|A \cap B|$ . Entonces, ¿qué expresiones están en este conjunto? Esta es una parte crucial de la solución, ¡así que hay que tomarse un tiempo para pensarlo antes de leer la respuesta de abajo! Para facilitar esto, se puede asumir primero que ni Bessie ni Elsie tienen la instrucción $*0$ , ya que no es demasiado difícil ver si $I(i, j)$ contiene la expresión $0$ y reduce el número de casos borde que hay que considerar.

Pista

¡Pensemos en la propiedad conmutativa !

Explicación detallada

Nota: Esta explicación presenta la solución de forma muy abstracta, ¡pero debería ser bastante intuitiva!

Consideremos las propiedades de una expresión después de aplicarle una instrucción:

$*d$ : todos los coeficientes deben ser múltiplos de $d$
$+x$ : el coeficiente de x es exactamente $1$ Llamemos a estos los rasgos de esa instrucción, y digamos que una instrucción X es violada por una instrucción posterior Y si, después de aplicar la instrucción Y, los rasgos de la instrucción X ya no se cumplen. Como ejemplo, sea la instrucción X $*2$ y la instrucción Y $+y$ . Después de aplicar la instrucción X a la expresión $x$ , obtenemos $2x$ , que satisface el rasgo de que todos los coeficientes deben ser múltiplos de 2. Sin embargo, después de aplicar la instrucción Y, obtenemos $2x + y$ , una expresión cuyos coeficientes ya no son todos pares; por lo tanto, la instrucción Y viola la instrucción X. De estas definiciones, obtenemos un hecho importante: dos operaciones que no se violan entre sí deben ser conmutativas (¡intentemos ver la intuición)!

Si una expresión está contenida en ambos conjuntos $A$ y $B$ , por definición se puede escribir tanto como $E(i - 1, j) \rightarrow a_i$ como $E(i, j - 1) \rightarrow b_j$ , y por lo tanto debe satisfacer los rasgos de $a_i$ y de $b_j$ . Así, tenemos que:

$a_i$ y $b_j$ son conmutativas
la expresión se puede escribir como $\text{[some expression]} \rightarrow a_i \rightarrow b_j$ (o $\text{[some expression]} \rightarrow b_j \rightarrow a_i$ ). Sin embargo, como esta expresión aún debe estar en $I(i, j)$ , vemos que $\text{[some expression]}$ debe estar en $I(i - 1, j - 1)$ , ya que ya colocamos tanto $a_i$ como $b_j$ al final de la secuencia de instrucciones. Por lo tanto, tenemos que $|A \cap B| = |I(i - 1, j - 1)|$ cuando $a_i$ y $b_j$ son conmutativas, y $0$ en caso contrario.

TL;DR

Si $a_i$ y $b_j$ son operaciones conmutativas (es decir, $\rightarrow a_i \rightarrow b_j$ hace lo mismo que $\rightarrow b_j \rightarrow a_i$ ), sobrecontamos el conjunto $I(i - 1, j - 1) \rightarrow a_i \rightarrow b_j$ . ¡Hay que recordar también el caso borde de la expresión $0$ (más detallado en el código más adelante)!

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int N = 2e3 + 1;
const int MOD = 1e9 + 7;
 
// suma y resta módulo
ll ad(ll &a, ll b) { return a = (a + b) % MOD; }
ll sb(ll &a, ll b) { return a = (((a - b) % MOD) + MOD) % MOD; }
 
// devuelve si c es un dígito de 1 a 9
bool digit(char c) { return '1' <= c && c <= '9'; }
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		cin >> n;
		vector<char> a(n + 1), b(n + 1);
		for (int i = 1; i <= n; i++) { cin >> a[i]; }
		for (int i = 1; i <= n; i++) { cin >> b[i]; }
 
		// zero[i][j] -> si 0 está en I(i, j)
		vector<vector<bool>> zero(n + 1, vector<bool>(n + 1));
		// I(0, 0) = {0}
		zero[0][0] = true;
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				if (!i && !j) continue;
				// I(i, j) contiene 0 si:
				// 1. a[i] o b[j] = 0
				// 2. I(i - 1, j) contiene 0 y a[i] no es +x
				// 3. I(i, j - 1) contiene 0 y b[j] no es +x
				zero[i][j] = a[i] == '0' || b[j] == '0' ||
				             i && zero[i - 1][j] && a[i] != '+' ||
				             j && zero[i][j - 1] && b[j] != '+';
			}
		}
 
		// dp[i][j] -> número de expresiones no nulas en I(i, j)
		vector<vector<ll>> dp(n + 1, vector<ll>(n + 1));
		dp[0][0] = 0;
		// |I(i, 0)| = |I(0, i)| = 1 ->
		// # de expresiones no nulas = 1 - # de expresiones nulas
		for (int i = 1; i <= n; i++) {
			dp[0][i] = !zero[0][i];
			dp[i][0] = !zero[i][0];
		}
 
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = 0;
				if (a[i] != '0') { ad(dp[i][j], dp[i - 1][j]); }
				if (a[i] == '+') { ad(dp[i][j], zero[i - 1][j]); }
				if (b[j] != '0') { ad(dp[i][j], dp[i][j - 1]); }
				if (b[j] == '+') { ad(dp[i][j], zero[i][j - 1]); }
				// restamos la intersección de A y B
				if (a[i] == '+' && b[j] == '+' || a[i] == '1' && b[j] == '+' ||
				    a[i] == '+' && b[j] == '1') {
					sb(dp[i][j], dp[i - 1][j - 1] + zero[i - 1][j - 1]);
				} else if (digit(a[i]) && digit(b[j])) {
					sb(dp[i][j], dp[i - 1][j - 1]);
				}
			}
		}
 
		cout << ad(dp[n][n], zero[n][n]) << '\n';
	}
}