UVa 10870 & 矩阵快速幂

时间：2023-03-09 20:01:28
UVa 10870 & 矩阵快速幂

题意：

　　求一个递推式（不好怎么概括。。）的函数的值。

　　即 f(n)=a1f(n-1)+a2f(n-2)+...+adf(n-d);

SOL：

　　根据矩阵乘法的定义我们可以很容易地构造出矩阵，每次乘法即可求出下一位f(n)的值并在距震中保存f(n)-----f(n-d+1)。

　　像我这种傻逼看错好几次运算法则的人 = =

　　第一道矩乘对着老人家模板打得几乎一模一样-----只是觉得他的写法比较优雅= =（虽然我感觉那么多memcpy会不会让常数很大。。。）

CODE：

　　

/*==========================================================================

# Last modified: 2016-03-03 21:11

# Filename: uva10870.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm> 

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector> 

#define lowbit(x) (x)&(-x)

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1] 

#define maxn 100

#define maxm 100000

#define pi 3.1415926535898

#define _e 2.718281828459

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull; 

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

typedef long long Matrix[maxn][maxn];

typedef long long Vector[maxn];

int n,m,d,sz;

void matrix_mul(Matrix A,Matrix B,Matrix res){

	Matrix C;

	memset(C,0,sizeof(C));

	FORP(i,0,sz-1)

		FORP(j,0,sz-1)

			FORP(k,0,sz-1)C[i][j]=(C[i][j]+A[i][k]*B[k][j])%m;

	memcpy(res,C,sizeof(C));

}

void matrix_pow(Matrix A,int n,Matrix res){

	Matrix a,r;

	memcpy(a,A,sizeof(a));

	memset(r,0,sizeof(r));

	FORP(i,0,sz-1) r[i][i]=1;

	while (n){

		if (n&1) matrix_mul(r,a,r);

		n >>= 1;

		matrix_mul(a,a,a);

	}

	memcpy(res,r,sizeof(r));

}

void transform(Vector d,Matrix A,Vector res){

	Vector r;

	memset(r,0,sizeof(r));

	FORP(i,0,sz-1)

		FORP(j,0,sz-1) r[j]=(r[j]+d[i]*A[i][j])%m;

	memcpy(res,r,sizeof(r));

}

int main(){

	while (scanf("%d%d%d",&d,&n,&m)!=EOF){

		if (d==0 && n==0 && m==0) return 0;

		Matrix A;

		Vector a,f;

		FORP(i,0,d-1) { read(a[i]); a[i]%=m;}

		FORM(i,d-1,0) { read(f[i]); f[i]%=m;}

		memset(A,0,sizeof(A));

		FORP(i,0,d-1) A[i][0]=a[i];

		FORP(i,1,d-1) A[i-1][i]=1;

		sz=d;

		matrix_pow(A,n-d,A);

		transform(f,A,f);

		cout << f[0] << endl;

	}

}

相关文章