uva10870

https://vjudge.net/problem/UVA-10870

裸的矩阵快速幂 注意系数矩阵在前面 因为系数矩阵为d*d 方程矩阵为d * 1 放反了就是d * 1 d * d 不符合矩阵乘法

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

struct mat {

    ll a[N][N];

} x, g;

int n, m, d;

ll a[N], f[N];

mat operator * (mat a, mat b)

{

    mat ret; memset(ret.a, , sizeof(ret.a));

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

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

            for(int k = ; k <= d; ++k) ret.a[i][j] = (ret.a[i][j] + a.a[i][k] % m * b.a[k][j] % m) % m;

    return ret;

}

void build()

{

    memset(x.a, , sizeof(x.a)); memset(g.a, , sizeof(g.a));

    for(int i = ; i <= d; ++i) x.a[i][] = f[d - i + ];

    for(int i = ; i <= d; ++i) g.a[][i] = a[i];

    for(int i = ; i <= d; ++i) g.a[i][i - ] = ;

}

mat power(mat A, int t)

{

    mat ret; memset(ret.a, , sizeof(ret.a));

    for(int i = ; i <= d; ++i) ret.a[i][i] = ;

    for(; t; t >>= , A = A * A) if(t & ) ret = ret * A;

    return ret;

}

int main()

{

    while(scanf("%d%d%d", &d, &n, &m))

    {

        if(n ==  && d ==  && m == ) break;

        for(int i = ; i <= d; ++i) scanf("%d", &a[i]), a[i] %= m;

        for(int i = ; i <= d; ++i) scanf("%d", &f[i]), f[i] %= m;

        if(n <= d)

        {

            printf("%d\n", f[n]);

            continue;

        }

        build();

        mat t = power(g, n - d);

        t = t * x;

        printf("%lld\n", t.a[][]);

    }

    return ;

}