题目描述
小 X 在上完生物课后对细胞的分裂产生了浓厚的兴趣。于是他决定做实验并
观察细胞分裂的规律。
他选取了一种特别的细胞，每天每个该细胞可以分裂出 x 1 个新的细胞。
小 X 决定第 i 天向培养皿中加入 i 个细胞（在实验开始前培养皿中无细胞）。
现在他想知道第 n 天培养皿中总共会有多少个细胞。
由于细胞总数可能很多，你只要告诉他总数对 w 取模的值即可。
输入格式
第一行三个正整数 n; x; w。
输出格式
一行一个数表示第 n 天的细胞总数对 w 取模的值。
样例输入
2 2 47
样例输出
4
2
数据范围
对于 30% 的数据，n ≤10^7
对于另外 10% 的数据，x = 1
对于 100% 的数据，1≤n≤2^63-1 1≤x,w≤2^31-1
题解：
仔细想一想思路还是比较清晰的
首先递推式F[i]=x*F[i-1]+i
那么需要转移的量为2个所以开三维，其中一维为i的辅助
可以写出：
F[i+1] i+1 1 = F[i] i 1 * x 0 0
1 1 0
0 1 1
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,x,mod;
struct node{
ll a[][];
node(){for(int i=;i<;i++)for(int j=;j<;j++)a[i][j]=;}
node(ll b[][]){for(int i=;i<;i++)for(int j=;j<;j++)a[i][j]=b[i][j];}
inline node operator *(const node p){
node tmp;
for(int i=;i<;i++)
for(int j=;j<;j++){
tmp.a[i][j]=;
for(int k=;k<;k++)
tmp.a[i][j]+=a[i][k]*p.a[k][j],tmp.a[i][j]%=mod;
}
return tmp;
}
};
ll work(){
ll t[][]={{,,},{,,},{,,}},sum[][]={{x,,},{,,},{,,}};
node S=node(t),T=node(sum);
while(n){
if(n&)S=S*T;
T=T*T;n>>=;
}
return S.a[][];
}
int main()
{
freopen("cell.in","r",stdin);
freopen("cell.out","w",stdout);
scanf("%lld%lld%lld",&n,&x,&mod);
printf("%lld\n",work());
return ;
}