看了这位学长的博客，所以想要记录一下其中涉及到的如何快速求等比数列的和（矩阵快速幂也可以快速求出，这里就不写了）；
链接：https://blog.csdn.net/keepcoral/article/details/80144750
假设我们现在知道了a1，q，n，叫我们求等比数列的和，如果这个和非常大，需要取模，所以我们也知道了mod。
即a1，q，n，mod是已知的。
补充一下数学知识，有时候吧我也会忘记：
an=a1*q^(n-1)，等比数列的和Sn=a1+a1*q+a1*q^2+...+a1*q^(n-1)=a1*(1+q+q^2+...+q^(n-1))=a1*(1-q^n)/(1-q);
这里主要是上面的这两个加粗的公式
在求和的时候我们先把a1提出来，咱们先算(1+q+q^2+...+q^(n-1))，这里主要是二分的思想
ll T(ll q,ll n) { if(n==1) return 1; ll date=T(q,n/2)%mod;//step1 date=(date+date*quick(q,n/2))%mod;//step2 if(n%2) date=(date+quick(q,n-1))%mod;//step3 return date; }
我在这里再添加一个例子：假如n为15；当递归到n==1时我们回溯；
递归顺序是n=15，n=7，n=3，n=1；
我们要求1+q+q^2+q^3+...+q^14;
我们回溯（退回去）。
n==3，step1:date=1 step2:date=1+q step3date=1+q+q^2;
n==7, step1:date=1+q+q^2 step2:date=1+q+q^2+q^3+q^4+q^5 step3:date=1+q+q^2+q^3+q^4+q^5+q^6
太长了，偷个懒
n==15,step1:date=1+...+q^6 step2:date=1+...+q^6+...+q^13 step3:date=1+...+q^14;
看上面的step1，step2，step3三个过程应该可以理解了吧。
代码：
#include<stdio.h> #include<string.h> #define mod 10000007 #define ll long long ll n,m,k,t; ll quick(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=a*ans%mod; a=a*a%mod; b>>=1; } return ans; } ll T(ll q,ll n) { if(n==1) return 1; ll date=T(q,n/2)%mod; date=(date+date*quick(q,n/2))%mod; if(n%2) date=(date+quick(q,n-1))%mod; return date; } int main() { ll q,n,a1; scanf("%lld%lld%lld",&a1,&q,&n); ll ans=T(q,n); ans=ans*a1%mod; printf("%lld",ans); return 0; }