Stamp Painting

Análisis oficial (C++) 

Solución

Esta es una solución similar a la del editorial oficial pero usa un Árbol de Segmentos para las transiciones. Recomiendo encarecidamente leer el editorial oficial además de esta solución.

Observemos las restricciones necesarias para que un ordenamiento de sellos sea válido. Debe haber al menos un segmento de longitud k o mayor. Podemos trabajar hacia atrás empezando desde este segmento. Quitamos este segmento de longitud $k$. Luego podemos quitar los segmentos a su izquierda y a su derecha porque, aunque no sean más largos que $k$, podemos asumir que se superpusieron con el segmento anterior que quitamos. Podemos quitar toda la pintura de esta forma.

Ahora solo necesitamos contar el número de ordenamientos con un segmento contiguo de longitud $k$ con el mismo color. En vez de esto, podemos usar conteo complementario y contar lo contrario con programación dinámica. Sea $dp[i]$ el número de ordenamientos para los primeros $i$ caracteres. Cuando $i$ es menor que $k$, $dp[i] = m^i$ ya que los primeros $i$ caracteres pueden ser cualquiera de los $m$ colores. Observemos que podemos agregar un segmento de longitud de hasta $k - 1$ de un solo color al final de un ordenamiento válido. Este segmento puede tener $m - 1$ colores (no podemos elegir el color que corresponde al segmento anterior porque los dos segmentos combinados pueden volverse más largos que $k$). Así, podemos enunciar las siguientes recurrencias.

Si $x < k$, entonces $dp[x]$ será $m^x$. En caso contrario, si $x >= k$, entonces $dp[x]$ será la suma de los últimos $k - 1$ estados de $dp$ multiplicada por $m - 1$. Más formalmente, podemos definir esta relación como:

Para calcular el segundo tipo de transición, podemos usar un Árbol de Segmentos. Podemos restar $dp[n]$ de $m^n$ (número total de pinturas) para obtener el número de pinturas válidas.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const ll MOD = 1e9 + 7;
 
// BeginCodeSnip{Segment Tree}
template <class T> struct SegTree {
	const T ID = 0;
	T cmb(T a, T b) { return (a + b) % MOD; }
	int n;
	vector<T> seg;
	SegTree(int _n) {
		for (n = 1; n < _n;) n *= 2;
		seg.assign(2 * n, ID);
	}
	void pull(int p) { seg[p] = cmb(seg[2 * p], seg[2 * p + 1]); }
	void upd(int p, T val) {
		seg[p += n] = val;
		for (p /= 2; p; p /= 2) pull(p);
	}
	T query(int l, int r) {
		T ra = ID, rb = ID;
		for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
			if (l & 1) ra = cmb(ra, seg[l++]);
			if (r & 1) rb = cmb(seg[--r], rb);
		}
		return cmb(ra, rb);
	}
};
// EndCodeSnip
 
/**
 * Binary exponentiation for fast exponentiation.
 * However, since n is small enough, you could also precalculate the powers of m
 * instead.
 */
ll bi_pow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) { ans = ans * a % MOD; }
		a = a * a % MOD;
		b /= 2;
	}
	return ans;
}
 
int main() {
	freopen("spainting.in", "r", stdin);
	freopen("spainting.out", "w", stdout);
	ll n, m, k;
	cin >> n >> m >> k;
 
	// Initialize segment tree
	SegTree<ll> dp(n + 1);
 
	for (int i = 1; i <= n; i++) {
		ll a;
		if (i < k) {  // If i is less than k, dp[i] will be a power of m
			a = bi_pow(m, i);
		} else {  // Otherwise, apply the second dp formula
			a = (m - 1) * dp.query(max(1, i - (int)k + 1), i - 1) % MOD;
		}
		dp.upd(i, a);
	}
	// Subtract dp[n] from the total number of segments
	cout << (bi_pow(m, n) + MOD - dp.query(n, n)) % MOD << endl;
}