「2015四校联考-一中」病毒分裂 - 折半递归/矩阵快速幂

题目大意

求 $(1+k+k^2+k^3+\cdots+k^{n-1})\bmod p$ 的值。

---

题目分析

这道题可以使用折半递归的方法做，具体的就是每次分一半，右边的就是左边的乘上$k^x$，每次丢掉一半，时间是$O(\log^2n)$的。

我们还可以使用矩阵快速幂做这道题。（本人构造的矩阵很智障？）

$$(1+k+k^2+k^3+\cdots+k^{n-1})=\begin{pmatrix} k && k && k \end{pmatrix}\times \begin{bmatrix} k && 0 && 0 \\ 0 && k && 0 \\ 0 && 1 && 1 \end{bmatrix}^{n-3}$$

最后加个$1$就可以了。
时间复杂度$O(\log n)$

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<ctime>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=5;
LL mod;
struct Matrix {
	LL n,m,a[maxn][maxn];
	Matrix(LL n,LL m) {
		init(n,m);
	}
	Matrix(LL n,LL m,char E) { //单位矩阵
		init(n,m);
		for(int i=1; i<=n; i++)a[i][i]=1;
	}
	void init(LL n,LL m) {
		this->n=n;
		this->m=m;
		memset(a,0,sizeof(a));
	}
	LL* operator [] (const LL x) {
		return a[x];
	}
	Matrix operator = (Matrix b) {
		init(b.n,b.m);
		for(int i=1; i<=b.n; i++)
			for(int j=1; j<=b.m; j++)
				a[i][j]=b[i][j];
	}
	Matrix operator * (Matrix b) {
		Matrix c(n,b.m);
		for(int i=1; i<=n; i++)
			for(int j=1; j<=b.m; j++)
				for(int k=1; k<=m; k++)
					c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
		return c;
	}
	void operator *= (Matrix& b) {
		*this=*this*b;
	}
	Matrix operator ^ (LL b) {
		Matrix ans(n,m,'e'),a=*this;
		while(b>0) {
			if(b&1)ans=ans*a;
			a*=a;
			b>>=1;
		}
		return ans;
	}
};
LL k,n;
int main() {
	k=Get_Int();
	n=Get_Int();
	mod=Get_Int();
	Matrix A(1,3),B(3,3);
	A[1][1]=A[1][2]=A[1][3]=k%mod;
	B[1][1]=B[2][2]=k%mod,B[3][2]=B[3][3]=1;
	A=A*(B^(n-3));
	printf("%lld\n",(A[1][2]+1)%mod);
	return 0;
}