Luogu T7152 细胞（递推，矩阵乘法，快速幂）

Description

小 X 在上完生物课后对细胞的分裂产生了浓厚的兴趣。于是他决定做实验并

观察细胞分裂的规律。

他选取了一种特别的细胞，每天每个该细胞可以分裂出 x − 1 个新的细胞。

小 X 决定第 i 天向培养皿中加入 i 个细胞（在实验开始前培养皿中无细胞）。

现在他想知道第 n 天培养皿中总共会有多少个细胞。

由于细胞总数可能很多，你只要告诉他总数对 w 取模的值即可。

Input

第一行三个正整数 n, x,w

Output

一行一个数表示第 n 天的细胞总数对 w 取模的值。

Sample Input

2 2 47

Sample Output

4

Http

Luogu（团队私有题目）:https://www.luogu.org/problem/show?pid=T7152

Source

递推，矩阵乘法，快速幂

解决思路

首先考虑数据范围较小的情况，令F[i]表示第i天培养皿中的细胞个数，那么我们可以轻易地推导出递推式：F[i]=x*F[i-1]+i 当然这样是过不了的，这道题的正确解法确实是递推，但是要用矩阵优化! 关于矩阵，可以到我的这篇文章：http://www.cnblogs.com/SYCstudio/p/7211050.html 我们在上面推出了递推式F[i]=x*F[i-1]+i，我们发现若要求出F[i]必须一遍一遍for，并且不能讲这个式子化简，若我们能找到一个式子F[i]=T*F[i-1]，岂不美哉？这样我们就可以直接得到F[n]=F[1]*T^(n-1)，这就可以用快速幂在logn范围内解决了。

矩阵正式这么一个美哉的式子，我们需要运用一些智慧来凑出T矩阵。 首先我们再回到F[i]=x*F[i-1]+i，这其中有两个变量F[i-1]和i，我们发现F[i-1]由F[i-2]推过来，而i则是每次递增常数1。所以，在把F变成矩阵后，我们可以确定这是一个三维矩阵，\[[原有细胞数，新加的细胞数，i递增的常数1]\],例如第一天就是[0,1,1]，第二天就是[1,2,1]，第三天就是[x+2,3,1],为了方便叙述，我们把该矩阵补成3*3的，即\[\begin{bmatrix} 原有的细胞数 & 第i天新加的细胞数 & i的递增常数1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}\] 那么接下来就是脑补出T矩阵啦！ 根据矩阵乘法的定义，我们可以得到T矩阵为：\[\begin{bmatrix} X & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix}\] 至于怎么得到的呢？说啦要靠脑补要靠从矩阵乘法的定义出发，用0和1来处理在某个位置是否要保留某个数，经过一系列yy然后我们就得到T啦。

接下来我们来检验一下T是否正确。 我们先有一个初值（即第一天）\[F_1=\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}\] 然后我们计算\[F_2=F_1*T=\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}*\begin{bmatrix} X & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix}=\begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}\] 发现没有，F2的第一行的三个数正好是我们上面的\[[原有细胞数，新加的细胞数，i递增的常数1]\] 如果不信，我们再计算几个\[F_3=F_2*T=\begin{bmatrix} 1 & 2 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}*\begin{bmatrix} X & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix}=\begin{bmatrix} x+2 & 3 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}\]\[F_4=F_3*T=\begin{bmatrix} x+2 & 3 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}*\begin{bmatrix} X & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix}=\begin{bmatrix} x^2+2x+3 & 4 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}\]\[F_5=F_4*T=\begin{bmatrix} x^2+2x+3 & 4 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}*\begin{bmatrix} X & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix}=\begin{bmatrix} x^3+2x^2+3x+4 & 5 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}\]这里强烈建议自己手动模拟一下

矩阵快速幂

既然我们已经有了如此妙啊的矩阵，那我们如果用for循环一个一个累乘岂不是浪费才华吗？看到幂的形式了没有？我们可以把我们再整数幂计算时用到的快速幂算法运用到矩阵上来。 那么这里就是要对矩阵重载一下*运算符就可以了，其他地方均与整数快速幂一致。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define ll long long ll n,X,Mod; class Matrix//定义一个矩阵结构体 { public: ll M[3][3]; Matrix()//初始化0 { for (int i=0;i<3;i++) for (int j=0;j<3;j++) M[i][j]=0; } Matrix(ll Arr[3][3])//用数组来初始化 { for (int i=0;i<3;i++) for (int j=0;j<3;j++) M[i][j]=Arr[i][j]; } }; Matrix operator * (Matrix A,Matrix B)//重载乘法运算符 { Matrix Ans; for (int i=0;i<3;i++) for (int j=0;j<3;j++) for (int k=0;k<3;k++) Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod; return Ans; } const int inf=2147483647; ll Pow(); int main()//无比简单的主函数 { cin>>n>>X>>Mod; cout<<Pow()<<endl; return 0; } ll Pow()//矩阵快速幂 { ll a[3][3]={{0,1,1},{0,0,0},{0,0,0}};//初始状态 ll b[3][3]={{X,0,0},{1,1,0},{0,1,1}};//用来使状态发生转移的矩阵，即文中提到的T Matrix A(a); Matrix B(b); while (n!=0) { if (n&1) { A=A*B;//注意这里的乘法顺序，矩阵乘法不满足交换律 } B=B*B; n=n>>1; } return A.M[0][0];//根据我们的定义，最后的值就在A.M[0][0] }

如果对你有帮助就点个赞吧！ 同时欢迎大佬到右边或下面发言指错。

转载于:https://www.cnblogs.com/SYCstudio/p/7156312.html

相关资源：JAVA上百实例源码以及开源项目