Skip to Content
CTRL K

Bots

Análisis oficial 

Implementación

#include <cassert>
#include <iostream>
#include <vector>
 
const int MOD = 1e9 + 7;
 
long long pow(long long base, long long exp) {
	assert(exp >= 0);
	base %= MOD;
	long long res = 1;
	while (exp > 0) {
		if (exp % 2 == 1)  // si n es impar
			res = res * base % MOD;
		base = base * base % MOD;
		exp /= 2;
	}
	return res;
}
 
long long mod_inv(long long n) { return pow(n, MOD - 2); }
 
int main() {
	int max_moves;
	std::cin >> max_moves;
 
	long long total_states = 1;
	long long curr_level = 1;
	for (int l = 1; l <= max_moves; l++) {
		curr_level = (curr_level * 2) % MOD;
		total_states = (total_states + curr_level) % MOD;
	}
 
	// hay que multiplicar por 2 para obtener la cantidad real de vértices de un solo hijo
	long long half_one_child_num = 1;
	for (int l = max_moves + 1; l <= 2 * max_moves; l++) {
		curr_level = (2 * curr_level - 2 * half_one_child_num) % MOD;
		total_states = (total_states + curr_level) % MOD;
 
		half_one_child_num = (half_one_child_num * l) % MOD;
		half_one_child_num = (half_one_child_num * mod_inv(l - max_moves)) % MOD;
	}
	std::cout << (total_states + MOD) % MOD << std::endl;
}
import java.io.*;
 
public class Bots {
	private static final int MOD = (int)Math.pow(10, 9) + 7;
	public static void main(String[] args) throws IOException {
		int max_moves = Integer.parseInt(
		    new BufferedReader(new InputStreamReader(System.in)).readLine());
 
		long total_states = 1;
		long curr_level = 1;
		for (int l = 1; l <= max_moves; l++) {
			curr_level = (curr_level * 2) % MOD;
			total_states = (total_states + curr_level) % MOD;
		}
 
		// hay que multiplicar por 2 para obtener la cantidad real de vértices de un solo hijo
		long half_one_child_num = 1;
		for (int l = max_moves + 1; l <= 2 * max_moves; l++) {
			curr_level = (2 * curr_level - 2 * half_one_child_num) % MOD;
			total_states = (total_states + curr_level) % MOD;
 
			half_one_child_num = (half_one_child_num * l) % MOD;
			half_one_child_num =
			    (half_one_child_num * modInv((long)l - max_moves)) % MOD;
		}
		System.out.println((total_states + MOD) % MOD);
	}
 
	private static long modInv(long n) { return pow(n, MOD - 2); }
 
	private static long pow(long base, long exp) {
		assert exp >= 0;
		base %= MOD;
		long res = 1;
		while (exp > 0) {
			if (exp % 2 == 1)  // si n es impar
				res = res * base % MOD;
			base = base * base % MOD;
			exp /= 2;  // dividir por dos
		}
		return res;
	}
}
MOD = int(1e9) + 7
 
 
def mod_inv(n: int):
	return pow(n, MOD - 2, MOD)
 
 
max_moves = int(input())
 
total_states = 1
curr_level = 1
for l in range(1, max_moves + 1):
	curr_level = (curr_level * 2) % MOD
	total_states = (total_states + curr_level) % MOD
 
# hay que multiplicar por 2 para obtener la cantidad real de vértices de un solo hijo
half_one_child_num = 1
for l in range(max_moves + 1, 2 * max_moves + 1):
	curr_level = (2 * curr_level - 2 * half_one_child_num) % MOD
	total_states = (total_states + curr_level) % MOD
	half_one_child_num = (half_one_child_num * l * mod_inv(l - max_moves)) % MOD
 
print(total_states)

Solución 2

Definamos primero una recurrencia de DP, con dp[b][r]\texttt{dp}[b][r] siendo la cantidad de estados únicos donde el bot azul hizo bb movimientos y el bot rojo hizo rr movimientos:

dp[b][r]=dp[b−1][r]+dp[b][r−1] \texttt{dp}[b][r]=\texttt{dp}[b - 1][r] + \texttt{dp}[b][r - 1]

Se sigue que la respuesta es la suma de todos los elementos de dp\texttt{dp}.

Así se podría ver dp\texttt{dp} para n=4n=4:

11111
12345
1361015
14102035
15153570

Notar que estos números son exactamente los mismos que los del triángulo de Pascal, ¡solo que un poco rotados! Estos números forman un cuadrado rotado de longitud n+1n+1 (de ahora en más xx), y podemos expresar su suma como

∑i=0x−1∑j=ix+i−1(ji) \sum_{i=0}^{x-1} \sum_{j=i}^{x+i-1} {j \choose i}

Usando la identidad del palo de hockey , vemos que esto es igual a

∑i=0x−1(x+ii+1)=∑i=1x(x+i−1i) \begin{align*} &\sum_{i=0}^{x-1} {x+i \choose i+1}\\ =&\sum_{i=1}^{x} {x+i-1 \choose i} \end{align*}

También sabemos por la identidad del palo de hockey que ∑i=0a(a+i−1i)=(2aa)\sum\limits_{i=0}^{a} {a+i-1 \choose i} = {2a \choose a}. Así, obtenemos que

∑i=1x(x+i−1i)=∑i=0x(x+i−1i)−(x+i−10)=(2xx)−1=(2n+2n+1)−1 \begin{align*} &\sum_{i=1}^{x} {x+i-1 \choose i}\\ =&\sum_{i=0}^{x} {x+i-1 \choose i} - {x+i-1 \choose 0}\\ =&{2x \choose x} - 1\\ =&{2n+2 \choose n+1} - 1 \end{align*}

Implementación 2

Complejidad temporal: O(Nlog⁡MOD)\mathcal{O}(N \log MOD)

#include <cassert>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
 
const int MOD = 1e9 + 7;
 
long long pow(long long base, long long exp) {
	assert(exp >= 0);
	base %= MOD;
	long long res = 1;
	while (exp > 0) {
		if (exp % 2 == 1)  // si n es impar
			res = res * base % MOD;
		base = base * base % MOD;
		exp /= 2;
	}
	return res;
}
 
long long mod_inv(long long n) { return pow(n, MOD - 2); }
 
int main() {
	int max_moves;
	std::cin >> max_moves;
 
	pair<int, int> res_binom{max_moves * 2 + 2, max_moves + 1};
	long long res_num = 1;
	for (int i = res_binom.first; i > res_binom.first - res_binom.second; i--) {
		res_num = res_num * i % MOD;
	}
	for (int i = 1; i <= res_binom.second; i++) {
		res_num = res_num * mod_inv(i) % MOD;
	}
	cout << res_num - 1 << endl;
}
import java.io.*;
 
public class Bots {
	private static final int MOD = (int)Math.pow(10, 9) + 7;
	public static void main(String[] args) throws IOException {
		int maxMoves = Integer.parseInt(
		    new BufferedReader(new InputStreamReader(System.in)).readLine());
 
		int[] resBinom = new int[] {2 * maxMoves + 2, maxMoves + 1};
		long resNum = 1;
		for (int i = resBinom[0]; i > resBinom[0] - resBinom[1]; i--) {
			resNum = resNum * i % MOD;
		}
		for (int i = 1; i <= resBinom[1]; i++) { resNum = resNum * modInv(i) % MOD; }
		System.out.println(resNum - 1);
	}
 
	private static long modInv(long n) { return pow(n, MOD - 2); }
 
	private static long pow(long base, long exp) {
		assert exp >= 0;
		base %= MOD;
		long res = 1;
		while (exp > 0) {
			if (exp % 2 == 1)  // si n es impar
				res = res * base % MOD;
			base = base * base % MOD;
			exp /= 2;  // dividir por dos
		}
		return res;
	}
}
MOD = int(1e9) + 7
 
 
def mod_inv(n: int):
	return pow(n, MOD - 2, MOD)
 
 
max_moves = int(input())
 
res_binom = [2 * max_moves + 2, max_moves + 1]
res_num = 1
for i in range(res_binom[0], res_binom[0] - res_binom[1], -1):
	res_num = (res_num * i) % MOD
for i in range(1, res_binom[1] + 1):
	res_num = (res_num * mod_inv(i)) % MOD
 
print(res_num - 1)
Fundamentos