UVA

题目描述

考虑递推关系式(f(n)=a_1*f(n-1)+a_2*f(n-2)+....+a_d*f(n-d))，计算(f(n)\%m)

Input

输入包含多组测试数据。每组数据第一行为三个整数(d,n,m(1<=d<=15,1<=n<=2^{31}-1,1<=m<=46340))。

第二行包含(d)个非负整数(a_1,a_2.....a_d)。第三行为(d)个非负整数(f(1),f(2).....f(d))。这些数字均不超过(2^{31}-1)。输入结束的标志是(d=n=m=0).

Output

对于每组数据，输出(f(n)\%m)

Sample Input

1 1 100
2
1
2 10 100
1 1
1 1
0 0 0 

Sample Output

1
55

非常经典的矩阵优化递推入门题。

由题意得：有初始矩阵(A_1)和递推矩阵(g)。

(A_1*g^{i-1}=A_i)。

一个(f(n))的值只与前(d)个的(f())值有关，所以，我们只用构造一个(d*d)的矩阵。

(g)=(egin{pmatrix} a_1 & a_2 & a_3 & cdots & a_d \ 1 & 0 & 0 & cdots & 0 \ 0 & 1 & 0 & cdots & 0 \vdots & vdots & vdots & ddots & vdots \ 0 & 0 & 0 & cdots & 0 \ end{pmatrix}，)(A_1)=(egin{pmatrix} f_d & 0 & 0 & cdots & 0 \ f_{d-1} & 0 & 0 & cdots & 0 \ f_{d-2} & 0 & 0 & cdots & 0 \vdots & vdots & vdots & ddots & vdots \ f_1 & 0 & 0 & cdots & 0 \ end{pmatrix})

最后，根据矩阵快速幂求解即可。

空间复杂度(O(d^2))，时间复杂度(O(d^2*log_n))。

代码如下

#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long
#define LL long long
#define u64 unsigned long long
#define reg register
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)
#define erep(i,G,x) for(reg int i=(G).Head[x]; i; i=(G).Nxt[i])

inline int Read() {
    int res = 0, f = 1;
    char c;
    while (c = getchar(), c < 48 || c > 57)if (c == '-')f = 0;
    do res = (res << 3) + (res << 1) + (c ^ 48);
    while (c = getchar(), c >= 48 && c <= 57);
    return f ? res : -res;
}

template<class T>inline bool Min(T &a, T const&b) {return a > b ? a = b, 1 : 0;}
template<class T>inline bool Max(T &a, T const&b) {return a < b ? a = b, 1 : 0;}

const int N = 5e5 + 5, M = 25, mod = 1e9 + 9;

struct Matrix {
    int Num[M][M];
    inline void Init(void) {memset(Num, 0, sizeof Num);}
};

int A[M], d, n, Mod;

Matrix mul(Matrix a, Matrix b) {
    Matrix Ans;
    Ans.Init();
    rep(k, 1, d)rep(i, 1, d)rep(j, 1, d) Ans.Num[i][j] = (Ans.Num[i][j] + (a.Num[i][k] * b.Num[k][j]) % Mod) % Mod;
    return Ans;
}

inline void _main(void) {
    while (~scanf("%lld %lld %lld", &d, &n, &Mod)) {
        if (!d && !n && !Mod)return;
        Matrix Ans, us, T;
        us.Init(), Ans.Init(), T.Init();
        rep(i, 1, d)us.Num[1][i] = Read();
        rep(i, 2, d)us.Num[i][i - 1] = 1;
        rep(i, 1, d)Ans.Num[d - i + 1][1] = Read();
        rep(i, 1, d)T.Num[i][i] = 1;
        if (n <= d) {
            printf("%lld
", Ans.Num[d - n + 1][1]);
            continue;
        }
        n = n - d;
        while (n) {
            if (n & 1)T = mul(T, us);
            us = mul(us, us);
            n >>= 1;
        }
        Ans = mul(T, Ans);
        printf("%lld
", Ans.Num[1][1] % Mod);
    }
}

signed main() {
#define offline1
#ifdef offline
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
    _main();
    fclose(stdin); fclose(stdout);
#else
    _main();
#endif
    return 0;
}