Skip to Content
CTRL K

Jeopardized Projects

Editorial oficial 

Explicación

Un detalle que nos empuja en la dirección correcta es que un caso de prueba posible puede tener consultas que piden un solo número concreto, como

100 100

Esto motiva un enfoque de suma de prefijos, donde calculamos la respuesta para cada entero posible y respondemos las consultas con un arreglo de sumas de prefijos.

Para contar de verdad el número de arreglos no palindrómicos que suman un entero (al que de ahora en adelante llamaremos xx), podemos usar conteo complementario.

Para contar el número total de arreglos que suman xx, a secas, evaluamos la siguiente sumatoria:

∑l=1x((x−l)+(l−1)l−1) \sum_{l=1}^x \binom{(x-l)+(l-1)}{l-1}

En esta sumatoria, sumamos sobre todas las longitudes ll posibles del arreglo, y luego usamos estrellas y barras  para contar cuántos arreglos de longitud ll suman xx. La resta inicial de ll es para tener en cuenta que todos los elementos deben ser positivos.

Esta expresión se simplifica entonces a

∑l=1x(x−1l−1)=∑l=0x−1(x−1l)=2x−1 \begin{align*} \sum_{l=1}^x \binom{x-1}{l-1} &= \sum_{l=0}^{x-1} \binom{x-1}{l} \\ &= \boxed{2^{x-1}} \end{align*}

Se aplica el teorema del binomio para simplificar la sumatoria.

Queda contar el número de arreglos palindrómicos que suman xx. Para esto hay que considerar dos casos: xx par y xx impar.

Si xx es par, entonces es posible tener un arreglo palindrómico de longitud par. Cada mitad debe sumar x2\frac{x}{2} y, como las dos son básicamente idénticas, hay 2x2−12^{\frac{x}{2}-1} arreglos palindrómicos posibles de esta forma. Sin embargo, también podemos formar un arreglo de longitud impar tomando primero un número par de xx y poniéndolo como elemento central. Esto nos da un total de

1+2x2−1+∑i=1x/2−12(x−2i)/2−1 1+2^{\frac{x}{2}-1}+\sum_{i=1}^{x/2-1} 2^{(x-2i)/2-1}

El 11 del frente es otro caso borde cuando ponemos todo xx en el medio. Pero de todos modos, ¡observemos que esto se simplifica a 2x22^{\frac{x}{2}}! Bastante elegante, ¿no?

Si xx es impar, en cambio, no podemos tener un arreglo palindrómico de longitud par. Solo podemos tomar una cantidad impar de xx y ponerla como centro, lo que nos da

1+∑i=0⌊x/2⌋−12(x−2i−1)/2−1 1+\sum_{i=0}^{\lfloor x/2 \rfloor-1} 2^{(x-2i-1)/2-1}

Esto también se simplifica como el anterior, solo que esta vez queda 2x−122^{\frac{x-1}{2}}.

Implementación

Complejidad temporal: O(Q+N)\mathcal{O}(Q+N), donde NN es el valor máximo de rr.

MOD = 10**9 + 7
MAX_VAL = 10**5
 
two_pows = [1]
for _ in range(1, MAX_VAL + 1):
	two_pows.append((two_pows[-1] * 2) % MOD)
 
pref_sums = [0]
for i in range(1, MAX_VAL + 1):
	if i % 2 == 0:
		nonpal_num = (two_pows[i - 1] - two_pows[i // 2]) % MOD
	else:
		nonpal_num = (two_pows[i - 1] - two_pows[(i - 1) // 2]) % MOD
	pref_sums.append((pref_sums[-1] + nonpal_num) % MOD)
 
for _ in range(int(input())):
	lo, hi = [int(i) for i in input().split()]
	print((pref_sums[hi] - pref_sums[lo - 1]) % MOD)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
const int MAX_SUM = 1e5;
int mod(long long a) { return (a + MOD) % MOD; }
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	vector<int> pow_two;
	vector<int> pref;
 
	// definimos potencias de dos hasta el valor máximo de suma para consultarlas después
	pow_two.push_back(1);
	for (int i = 1; i < MAX_SUM + 1; i++) {
		pow_two.push_back((pow_two.back() * 2) % MOD);
	}
 
	// cantidad de soluciones de prefijo en cada i
	pref.push_back(0);
	for (int i = 1; i < MAX_SUM + 1; i++) {
		pref.push_back(mod(pref.back() + mod(pow_two[i - 1] - pow_two[i / 2])));
	}
 
	int tests = 0;
	cin >> tests;
 
	for (int i = 0; i < tests; i++) {
		int l, r;
		cin >> l >> r;
 
		cout << mod(pref[r] - pref[l - 1]) << "\n";
	}
}
Fundamentos