【题解】细胞

【题目描述】
小 X 在上完生物课后对细胞的分裂产生了浓厚的兴趣。于是他决定做实验并观察细
胞分裂的规律。
他选取了一种特别的细胞，每天每个该细胞可以分裂出 $x-1$ 个新的细胞。
小 X 决定第 i 天向培养皿中加入 $i$ 个细胞（在实验开始前培养皿中无细胞）。
现在他想知道第 n 天培养皿中总共会有多少个细胞。
由于细胞总数可能很多，你只要告诉他总数对 w 取模的值即可。
【输入格式】
第一行三个正整数 $n,x,w$。
【输出格式】
一行一个数表示第 n 天的细胞总数对 w 取模的值。
【样例输入】
2 2 47
【样例输出】
4
【数据范围】
对于 30% 的数据，$n<=10^7$。
对于另外 10% 的数据，$x=1$。
对于 100% 的数据，1<=n<=2⁶³ -1,1≤$x$,$w$≤2³¹ -1。
题目保证 $x-1 和 w$互质。

考场上遇见这题，首先看到这巨大的数据，我们自然而然地想到了数学。
经过，推导我们发现：第 $n+1$天的细胞个数为 $x^n+$$2$$x$^n-1 +….+$n+1$
然后经过一系列的差分操作，我们得到： $x$ⁿ⁺²-$x$-$(x-1)(n+1)$$/$ $(x-1)*(x-1)$ $mod$$w$
而这样，我们自然而然地想到了快速幂，用乘法逆元维护一下就行了。
code：

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
unsigned long long n,x,w;
void exgcd(unsigned long long a,unsigned long long b,int& x,int& y){
    if(b==0){x=1;y=0;return;}
    exgcd(b,a%b,y,x);y-=(a/b)*x;    
}

unsigned long long inv(unsigned long long x,unsigned long long mod){
    int u,v;
    exgcd(x,mod,u,v);
    u=(u+mod)%mod;
    return u;
}

unsigned long long multiply_64bit(unsigned long long a,unsigned long long b,unsigned long long mod){
    unsigned long long ans=0,power=a;
    while(b){
        if(b&1){
            ans+=power;
            ans%=mod;
        }
        power<<=1;
        power%=mod;
        b>>=1;
    }
    return ans%mod;
}

unsigned long long qpow(int a,unsigned long long b,unsigned long long mod){
    unsigned long long power=a,ans=1;
    while(b){
        if(b&1){
            ans=multiply_64bit(power,ans,mod);
        }
        power=multiply_64bit(power,power,mod);
        power%=mod;
        b>>=1;
    }
    return ans%mod;
}

int main(){
    freopen("cell.in","r",stdin);
    freopen("cell.out","w",stdout);
    cin>>n>>x>>w;
    unsigned long long x1=(qpow(x,n+1,w)+n%w-multiply_64bit(n+1,x,w))%w;
    unsigned long long x2=((unsigned long long)(x-1)*(x-1))%w;
    unsigned long long x3=inv(x2,w);
    cout<<multiply_64bit(x1,x3,w)<<endl;
    return 0;
}         

但是，我们考试中没有保证 $x-1 和 w$互质这个条件，那怎么做呢？
首先，我们得到了=$f（k）=xf(k-1)+k$。
但由于递推过于漫长，我们想到了矩阵快速幂。

于是，就可以求解了

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
int mod;
struct matrix{
    int a[3][3];
    matrix(){memset(a,0,sizeof(a));}
    int* operator [](int x){return a[x];}
    matrix operator *(matrix &b){
        matrix c;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++)c[i][k]=(c[i][k]+1ll*a[i][j]*b[j][k])%mod;
        return c;
    }
}S,T;
int main(){
    freopen("cell.in","r",stdin);
    freopen("cell.out","w",stdout);
    lol n=gl();T[0][0]=gi();mod=gi();
    S[0][1]=S[0][2]=T[1][0]=T[1][1]=T[2][1]=T[2][2]=1;
    while(n){
        if(n&1)S=S*T;
        T=T*T;
        n>>=1;
    }
    printf("%d",S[0][0]);
    return 0;
}

于是，这题就完美地解决了。
我才不会告诉你这不是我的代码