10870 Recurrences
Consider recurrent functions of the following form:
f(n) = a1f(n ?? 1) + a2f(n ?? 2) + a3f(n ?? 3) + : : : + adf(n ?? d); for n > d;
where a1, a2, …, ad are arbitrary constants.
A famous example is the Fibonacci sequence, defined as: f(1) = 1, f(2) = 1, f(n) = f(n ?? 1) +
f(n ?? 2). Here d = 2, a1 = 1, a2 = 1.
Every such function is completely described by specifying d (which is called the order of recurrence),
values of d coefficients: a1, a2, …, ad, and values of f(1), f(2), …, f(d). You’ll be given these numbers,
and two integers n and m. Your program’s job is to compute f(n) modulo m.
Input
Input file contains several test cases. Each test case begins with three integers: d, n, m, followed by
two sets of d non-negative integers. The first set contains coefficients: a1, a2, …, ad. The second set
gives values of f(1), f(2), …, f(d).
You can assume that: 1  d  15, 1  n  231 ?? 1, 1  m  46340. All numbers in the input will
fit in signed 32-bit integer.
Input is terminated by line containing three zeroes instead of d, n, m. Two consecutive test cases
are separated by a blank line.
Output
For each test case, print the value of f(n)( modm) on a separate line. It must be a non-negative integer,
less than m.
Sample Input
1 1 100
21
2 10 100
1 1
1 1
3 2147483647 12345
12345678 0 12345
1 2 3
0 0 0
Sample Output
1
55
423

题意：

       考虑线性递推关系：f(n)=a1*f(n-1)+a2*f(n-2)+…+ad*f(n-d)。给出d，n，m，a1，a2，…，ad，f(1)，f(2)，…，f(d)，计算f(n)除以m的余数。

分析：

       构造递推关系式：Fn=Fn-1 * A。

其中，Fn=(f(n-d+1),f(n-d+2),…,f(n))

而矩阵A将由以下代码进行构造：

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];

 1 #include<stdio.h> 2 #include<string.h> 3 typedef struct{ 4    long long Mat[16][16]; 5 }MAT; 6 long long n,MOD,d; 7 MAT mul(MAT a,MAT b){ 8    MAT c; 9    memset(c.Mat,0,sizeof(c.Mat));10    for(int i = 1 ; i <= d ; i++)11    for(int j = 1 ; j <= d ; j++)12    for(int k = 1 ; k <= d ; k++)13    c.Mat[i][j] = (c.Mat[i][j] + a.Mat[i][k] * b.Mat[k][j]) % MOD;14    return c;15 }16 MAT Quick_pow(MAT a,long long b){17    MAT c; memset(c.Mat,0,sizeof(c.Mat));18    for(int i = 1 ; i <= d ; i++) c.Mat[i][i] = 1;19    while(b){20       if(b & 1) c = mul(c,a);21       a = mul(a,a);22       b >>= 1;23    }24    return c;25 }26 int main(){27    long long D[16],F[16],i;28    MAT A;29    while(~scanf("%lld %lld %lld",&d,&n,&MOD) && d + n + MOD){30       for(i = 1 ; i <= d ; i++) {31          scanf("%lld",&D[i]);32          D[i] %= MOD;33       }34       for(i = 1 ; i <= d ; i ++) {35          scanf("%lld",&F[i]);36          F[i] %= MOD;37       }38       if(n <= d){39          printf("%lld\n",F[n]);40          continue;41       }42       memset(A.Mat,0,sizeof(A.Mat));43       int x = 2,y = 1;44       for(i = 2 ; i <= d ; i++) A.Mat[x][y] = 1,x++,y++;45       for(i = 1 ; i <= d ; i++) A.Mat[i][d] = D[d - i + 1];46       A = Quick_pow(A,n - 1);47       long long Ans = 0;48       for(i = 1 ; i <= d ; i++){49          Ans += F[i] * A.Mat[i][1];50          Ans %= MOD;51       }52       printf("%lld\n",Ans);53    }54    return 0;55 }

View Code

UVa10870