大概您打算使用快速指数递归来计算 r ^ n

Presumably you're proposing to compute r^n with the fast exponentiation recurrence

E(r, 0) = 1
E(r, n) = E(r*r, n/2)         if n is even
          r * E(r*r, (n-1)/2) if n is odd.

我们可以为 1 + r + r ^ 2 + ... + r ^ n 构建类似的直接递归.

We can construct a similar direct recurrence for 1 + r + r^2 + ... + r^n.

F(r, 0) = 1
F(r, n) = (1 + r) * F(r*r, (n-1)/2)       if n is odd
          1 + (r + r*r) * F(r*r, (n-2)/2) if n is even.

所有计算当然应该使用mod M .

All calculations should be done mod M, of course.