uva10870 递推关系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, defned 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 coefcients: 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 fle contains several test cases. Each test case begins with three integers: d, n, m, followed by
two sets of d non-negative integers. The frst set contains coefcients: 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
ft 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)( mod m) 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) +…… + an*f(n-d),当他是斐波那契数列时d=2,a1=a2=1，计算f(n)对m取余，这是一个适用范围很广的模型，要多看几遍
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 30;
ll sz,mod,f[maxn],a[maxn],ans[maxn];
struct mtx{
    ll v[maxn][maxn];
    void clear(){
        memset(v,0,sizeof(v));
    }
    mtx mul(mtx A,mtx B){
        mtx C;
        C.clear();
        for(int i = 1;i <= sz;i++){
            for(int j = 1;j <= sz;j++){
                for(int k = 1;k <= sz;k++){
                    C.v[i][j] = (C.v[i][j] + A.v[i][k]*B.v[k][j]) % mod;
                }
            }
        }
        return C;
    }
    mtx pow(mtx A,int n){
        mtx R;
        R.clear();
        for(int i = 1;i <= sz;i++) R.v[i][i] = 1;
        while(n){
            if(n&1) R = R.mul(R,A);
            n >>= 1;
            A = A.mul(A,A);
        }
        return R;
    }
    void get_tr(mtx A){
        for(int i = 1;i <= sz;i++){
            for(int j = 1;j <= sz;j++){
                ans[j] = (ans[j] + f[i]*A.v[i][j]) % mod;
            }
        }
    }
};
int main(){
    ll d,n,m;
   while(cin >> d >> n >> m && d) {
       mtx A;
    for(int i = 1; i <= d; i++) { cin >> a[i]; a[i] %= m; }
    for(int i = d; i >= 1; i--) { cin >> f[i]; f[i] %= m; }
    A.clear();
    memset(ans,0,sizeof(ans));
    for(int i = 1; i <= d; i++) A.v[i][1] = a[i];
    for(int i = 2; i <= d; i++) A.v[i-1][i] = 1;

    sz = d;
    mod = m;
    A = A.pow(A,n-d);
    A.get_tr(A);
    cout << ans[1] << endl;
  }
    return 0;
}

uva10870 递推关系Recurrences

推荐阅读