BZOJ 2326: [HNOI2011]数学作业(矩阵乘法)

传送门

解题思路

　　NOIp前看到的一道题，当时想了很久没想出来，NOIp后拿出来看竟然想出来了。注意到有递推\(f[i]=f[i-1]*poww[i]+i\)，\(f[i]\)表示\(1-i\)连接起来组成的数字，\(poww[i]\)表示\(10\)的\(i\)的位数次幂，发现这个可以用矩阵快速幂优化，\([f[i],i+1,1]\)，转移到\([f[i+1],i+2,1]\)，要做\(n\)的位数次快速幂，每次修改一下转移矩阵中\(poww\)的值就行了。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define int long long

using namespace std;

typedef long long LL;

LL n,ans,poww[20]={1};

int MOD,wei;

struct Matrix{

	LL a[4][4];

	void clear(){memset(a,0,sizeof(a));}

	friend Matrix operator*(const Matrix A,const Matrix B){

		Matrix ret;ret.clear();

		for(int i=1;i<=3;i++)

			for(int j=1;j<=3;j++)

				for(int k=1;k<=3;k++)

					(ret.a[i][j]+=(LL)A.a[i][k]*B.a[k][j]%MOD)%=MOD;

		return ret;

	}

}pre,A;

Matrix fast_pow(Matrix x,LL y){

	Matrix ret;ret.clear();ret.a[1][1]=ret.a[2][2]=ret.a[3][3]=1;

	for(;y;y>>=1){

		if(y&1) ret=ret*x;

		x=x*x;

	}

	return ret;

}

signed main(){

	scanf("%lld%lld",&n,&MOD);LL nn=n;

	while(n) n/=10,wei++;

	for(int i=1;i<=18;i++) poww[i]=poww[i-1]*10;

	A.a[2][1]=A.a[2][2]=A.a[3][2]=A.a[3][3]=1;pre.a[1][2]=pre.a[1][3]=1;

	for(int i=1;i<wei;i++) {

		A.a[1][1]=poww[i]%MOD;

		pre=pre*fast_pow(A,poww[i]-poww[i-1]);

	}A.a[1][1]=poww[wei]%MOD;

	pre=pre*fast_pow(A,nn-poww[wei-1]+1);

	printf("%lld\n",pre.a[1][1]);

	return 0;

}