Tu idea es correcta.
La solución es N ^ 1 + N ^ 2 +… + N ^ L = N * (N ^ L – 1) / (N-1).
Calcular el numerador mod 1000000007 es fácil pero no podemos dividirlo con (N-1). Ahora, dado que 1000000007 es primo, es coprimo con (N-1) y, por lo tanto, existe el inverso de (N-1) mod 1000000007. Podemos encontrarlo con un algoritmo euclidiano extendido y multiplicarlo con N * (N ^ L – 1) para obtener la respuesta.
Puede leer el algoritmo aquí: algoritmo euclidiano extendido
- ¿Cuáles son algunos algoritmos rápidos para calcular la enésima potencia de un número?
- ¿Cuál es el significado del lema de Schwartz-Zippel?
- ¿Cuáles son las aplicaciones de los derivados en informática?
- ¿Cuáles son algunos compromisos fundamentales en informática?
- ¿Por qué la gente siempre critica un doctorado en CS? ¿Por qué existe el título cuando bloquea las oportunidades profesionales?
Una implementación eficiente de inversa modular es la siguiente:
typedef long long ll; ll extendedEuclid(ll a, ll b, ll *x, ll *y) {
ll t, d;
if (b == 0) {
*x = 1; *y = 0; return a;
}
d = extendedEuclid(b, a % b, x, y);
t = *x; *x = *y; *y = t - (a/b)*(*y);
return d;
} ll modInverse(ll a, ll n) {
ll x, y;
extendedEuclid(a, n, &x, &y);
return (x < 0) ? (x + n) : x;
}
typedef long long ll; ll extendedEuclid(ll a, ll b, ll *x, ll *y) {
ll t, d;
if (b == 0) {
*x = 1; *y = 0; return a;
}
d = extendedEuclid(b, a % b, x, y);
t = *x; *x = *y; *y = t - (a/b)*(*y);
return d;
} ll modInverse(ll a, ll n) {
ll x, y;
extendedEuclid(a, n, &x, &y);
return (x < 0) ? (x + n) : x;
}
typedef long long ll; ll extendedEuclid(ll a, ll b, ll *x, ll *y) {
ll t, d;
if (b == 0) {
*x = 1; *y = 0; return a;
}
d = extendedEuclid(b, a % b, x, y);
t = *x; *x = *y; *y = t - (a/b)*(*y);
return d;
} ll modInverse(ll a, ll n) {
ll x, y;
extendedEuclid(a, n, &x, &y);
return (x < 0) ? (x + n) : x;
}
