Hint 1 : \(1 + x + x^2 + ... + x^n = \dfrac{x^{n+1}-1}{x-1}\)

Hint 2 : \(a\%b=c \to (k*a) \% (k*b) = k*c\)

Hint3 : Answer = \((1 + x + x^2 + ... + x^n) \% m = \dfrac{x^{n+1}-1}{x-1} \%m\)

Answer = \(\dfrac{x^{n+1}-1}{x-1} \%m \to\) Answer \(*k = \dfrac{(x^{n+1}-1)*k}{(x-1)} \% (m*k)\)

\(k=x-1 \to\) Answer \(*(x-1) = (x^{n+1}-1) \% (m*(x-1)) \to\) Answer = \(\dfrac {(x^{n+1}-1) \% (m*(x-1))}{x-1}\)

Hint 4: Dựa vào bài MOD1, MOD2 để tính \((x^{n+1}-1) \% (m*(x-1))\)

Mình xin trình bài lời giải bài này theo 2 cách như sau:

Cách 1: Chia để trị :

Đặt \(G(p,n)=1+p+...+p^{n}\rightarrow (1)\).

Công việc tiếp theo của chúng ta là đi tính \(G(p,n)\), và chúng được thực hiện như sau:

Ta có: \(G(p,n)=\left\{\begin{matrix} 1, \text{ với }n=0 \\ 1+p, \text{ với } n=1 \\ 1 + p*G(p,n-1), \text{ với } n \text{ lẻ } \\(1+p^{\frac{n}{2}})[G(p,\frac{n}{2})-1]+1=(1+p^{\frac{n}{2}})(1+p+...+p^{\frac{n}{2}}-1)+1, \text{ với } n \text{ chẵn }\end{matrix}\right.\)

Và độ phức tạp để tính \(G(p,n)\) là \(O(log(n))\)

Và các bạn có thể tham khảo code tại đây: Link

Cách 2: nhân ma trận.

Từ \((1)\implies G(p,n+1) = G(p,n)*p+1\)

Đặt \(F[n]=G(p,n)\). Khi đó ta có: \(F[n+1]=p * F[n]+1\)

\(\implies \begin{pmatrix}F[n] & 1\end{pmatrix}.\begin{pmatrix}p & 0 \\ 1 & 1\end{pmatrix} = \begin{pmatrix}F[n+1] & 1\end{pmatrix}\)

Đến đây, đặt \(p_n=\begin{pmatrix}F[n] & 1\end{pmatrix}\). và \(M=\begin{pmatrix}p & 0 \\ 1 & 1\end{pmatrix}\). Ta có: \(p_{n+1}=p_n.M=p_{n-1}.M^{2}=...=p_0.M^n\). Với \(p_0=\begin{pmatrix}1 & 1\end{pmatrix}\)

Đến đây sử dụng luỹ thừa nhị phân trên ma trận là ta đã giải quyết xong bài toán.

Các bạn có thể tham khảo code tại đây:Link