[ABC293E] Geometric Progression 题解

· · 题解

[ABC293E] Geometric Progression 题解

题意

给定 a,n,m，求

\sum\limits_{i=1}^{n-1}a^i\bmod{m}

分析

我们每次运用乘法分配律，每次提取公因式，下面以 n=5 来举例

\begin{aligned} \\&1+a^1+a^2+a^3+a^4 \\&=1+a(1+a^1+a^2+a^3) \\&=1+a(1+a(1+a^1+a^2)) \\&=1+a(1+a(1+a(1+a))) \end{aligned}

显然，就是做 n-1 次 \times a+1。

但是,1\leq n\leq 10^{12}，会 TLE。

我们考虑：

把 f_0=1，

则 f_i=f_{i-1}\times a+1，

所以答案为 f_{n-1}。

而第二个式子可以用矩阵快速幂来求，所以时间为 O(\log{n})，可过。

矩阵为：

\begin{bmatrix} 1,1 \end{bmatrix}\times \begin{bmatrix} a,0 \\1,1 \end{bmatrix}^{n-1}

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
const int N=3;
int x,n,mod;
struct qwq{
    int n,m,num[N][N];
}ans,a;
void print(qwq x){
    for(int i=1;i<=x.n;puts(""),i++)
        for(int j=1;j<=x.m;j++)
            printf("%lld ",x.num[i][j]);
    return;
}
qwq operator*(const qwq &x,const qwq &y){
    qwq c;c.n=x.n;c.m=y.m;
    for(int i=1;i<=c.n;i++)
        for(int j=1;j<=c.m;j++)
            c.num[i][j]=0;
    for(int i=1;i<=x.n;i++)
        for(int j=1;j<=y.m;j++)
            for(int k=1;k<=x.m;k++) 
                (c.num[i][j]+=x.num[i][k]*y.num[k][j]%mod)%=mod;
    return c;
}
qwq ksm(qwq a,int b){
    qwq t;t.n=t.m=2;
    t.num[1][1]=t.num[2][2]=1;
    t.num[1][2]=t.num[2][1]=0;
    for(;b;b>>=1,a=a*a)if(b&1)t=t*a;
    return t;
}
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    x=read();n=read()-1;mod=read();
    ans.n=1,ans.m=2;
    ans.num[1][1]=ans.num[1][2]=1;
    a.n=a.m=2;
    a.num[1][1]=x;a.num[2][1]=a.num[2][2]=1;
    a.num[1][2]=0;
    qwq t=ksm(a,n);
    ans=ans*t;
    printf("%lld\n",ans.num[1][1]);
    return 0;
}