Calcul 1^X + 2^X + ... + N^X mod 1000000007
Est-il un algorithme pour calculer (1^x + 2^x + 3^x + ... + n^x) mod 1000000007?
Remarque: a^b est le b-ième puissance d'un.
Les contraintes sont 1 <= n <= 10^16, 1 <= x <= 1000. De sorte que la valeur de N est très grand.
je ne peut résoudre pour O(m log m) si m = 1000000007. Elle est très lente car la limite de temps est de 2 secondes.
avez-vous un algorithme efficace?
il y a eu un commentaire selon lequel il pourrait s'agir d'un double de cette question, mais c'est définitivement différent.
3 réponses
Vous pouvez somme la série
1**X + 2**X + ... + N**X
avec l'aide de formule de Faulhaber et vous obtiendrez un polynôme avec un X + 1 pouvoir de calculer pour l'arbitraire N.
Si vous ne voulez pas de calculer Nombres De Bernoulli, vous pouvez trouver le polynôme en résolvant X + 2équations linéaires (pour N = 1, N = 2, N = 3, ..., N = X + 2) qui est une méthode plus lente, mais plus facile à mettre en œuvre.
prenons un exemple X = 2. Dans ce cas, nous avons un X + 1 = 3 commander polynôme:
A*N**3 + B*N**2 + C*N + D
Les équations linéaires sont
A + B + C + D = 1 = 1
A*8 + B*4 + C*2 + D = 1 + 4 = 5
A*27 + B*9 + C*3 + D = 1 + 4 + 9 = 14
A*64 + B*16 + C*4 + D = 1 + 4 + 9 + 16 = 30
après avoir résolu les équations nous obtiendrons
A = 1/3
B = 1/2
C = 1/6
D = 0
La formule finale est
1**2 + 2**2 + ... + N**2 == N**3 / 3 + N**2 / 2 + N / 6
Maintenant, tout ce que vous avez à faire est de mettre un arbitraire grandN dans la formule. Jusqu'à présent, l'algorithme a O(X**2) complexité (puisqu'elle ne dépend pas de N).
Il y a quelques façons d'accélérer l'exponentiation modulaire. À partir d'ici, je vais utiliser ** pour désigner une "exponentiate" et % pour désigner une "module".
D'abord quelques observations. C'est toujours le cas que (a * b) % m((a % m) * (b % m)) % m. Il est également toujours le cas que a ** n est le même que (a ** floor(n / 2)) * (a ** (n - floor(n/2)). Cela signifie que pour un exposant < = 1000, nous pouvons toujours compléter l'exponentiation dans au plus 20 multiplications (et 21 mods).
nous pouvons également passer pas mal de temps les calculs, car (a ** b) % m est le même que ((a % m) ** b) % m et si m est significativement plus bas que n, Nous avons simplement des sommes répétées multiples, avec une "queue" d'une répétition partielle.
je pense que la réponse de Vatine est probablement la voie à suivre, mais j'ai déjà tapé et il peut être utile, pour le présent ou pour quelqu'un d'autre similaire problème.
Je n'ai pas le temps ce matin pour une réponse détaillée, mais considérez ceci.
1^2 + 2^2 + 3^2 + ... + n^2 prendrait O( n) étapes pour calculer directement.
Cependant, c'est l'équivalent de (n(n+1)(2n+1)/6), qui peut être calculée en
O (1) time. Une équivalence similaire existe pour toute puissance intégrale supérieure
x.
Il y a peut être une solution générale à ce problème; je n'en connais pas, et Wolfram Alpha ne semble pas en connaître un non plus. Toutefois, dans général l'expression équivalente est de degré x+1, et peut être travaillé en calculant quelques valeurs d'échantillon et en résolvant un ensemble de linéaire équations pour les coefficients.
Cependant, ce serait difficile pour les gros x, comme 1000, comme dans votre problème, et ne pourrait probablement pas être fait dans les 2 secondes.
peut-être quelqu'un qui en sait plus que moi sur les maths peut transformer ça en une solution réalisable?
Edit: Oups, j'voir Fabian Pijcke avais déjà posté un lien utile sur formule de Faulhaber avant que je poste.