UVA10870递推关系（矩阵乘法）

题意：

给以个递推f(n) = a1 f(n - 1) + a2 f(n - 2) + a3 f(n - 3) + ... + ad f(n - d), for n > d.，给你n,d,a1,a2..ad ,f[1],f[2]..f[d],让你求f[n]%m.

思路：

比较基础的矩阵题目，每次都构造一个d*d的矩阵，然后用快速幂求出来它的n-1次幂，然后在求出乘积就行了，简单构造，没有什么坑点。



#include<stdio.h>

#include<string.h>

typedef struct

{

long long Mat[16][16];

}MAT;

long long n ,MOD ,d;

MAT mm(MAT a ,MAT b)

{

MAT c;

memset(c.Mat ,0 ,sizeof(c.Mat));

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

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

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

c.Mat[i][j] = (c.Mat[i][j] + a.Mat[i][k] * b.Mat[k][j])%MOD;

return c;

}

MAT Quick(MAT a ,long long b)

{

MAT c;

memset(c.Mat ,0 ,sizeof(c.Mat));

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

c.Mat[i][i] = 1;

while(b)

{

if(b&1) c = mm(c ,a);

a = mm(a ,a);

b>>=1;

}

return c;

}

int main ()

{

long long D[16] ,F[16] ,i;

MAT A;

while(~scanf("%lld %lld %lld" ,&d ,&n ,&MOD) && d + n + MOD)

{

for(i = 1 ;i <= d ;i ++)

{

scanf("%lld" ,&D[i]);

D[i] %= MOD;

}

for(i = 1 ;i <= d ;i ++)

{

scanf("%lld" ,&F[i]);

F[i] %= MOD;

}

if(n <= d)

{

printf("%lld\n" ,F[n]);

continue;

}

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

int x = 2 ,y = 1;

for(i = 2 ;i <= d ;i ++)

{

A.Mat[x][y] = 1;

x ++ ,y ++;

}

for(i = 1 ;i <= d ;i ++)

A.Mat[i][d] = D[d-i+1];





A = Quick(A ,n - 1);

long long Ans = 0;

for(i = 1 ;i <= d ;i ++)

{

Ans += F[i] * A.Mat[i][1];

Ans %= MOD;

}

printf("%lld\n" ,Ans);

}

return 0;

}

巴特西

UVA10870递推关系（矩阵乘法）

最新文章

热门文章