FZU Problem 1692 Key problem(循环矩阵)

循环矩阵，这里有解说：http://wenku.baidu.com/link?

url=zcJ-sxrj0QDqzz8xCnHTnB7gxjoNRyOZzS4_4ZA22c8Bs9inYn6vVkqTVr_w-riLa8oRnYA9SRcCZ9f4UciCUNGeNAG4dCGclYRPS18YLGa

推出第一层以下依据性质就能够得到。

#include <set>
#include <map>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>

#define eps 1e-8
#define pi acos(-1.0)

#define LL __int64

using namespace std;


const int maxn = 110;

LL a[maxn], b[maxn], f[maxn];

LL mod, n;

void mul(LL a[], LL b[])
{
    LL c[maxn];
    memset(c, 0, sizeof(c));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) c[i] = (a[j]*b[(i-j+n)%n]+c[i])%mod;
    memcpy(a, c, sizeof(c));
}

void pow_mod(LL a[], LL b)
{
    LL c[maxn];
    memset(c, 0, sizeof(c));
    c[0] = 1LL;
    while(b)
    {
        if(b&1) mul(c, a);
        mul(a, a);
        b >>= 1;
    }
    memcpy(a, c, sizeof(c));
}

int main()
{
    int T;
    cin>>T;
    LL m, l, r;
    while(T--)
    {
        cin>>n>>m>>l>>r>>mod;
        for(int i = 0;i < n;i++)  cin>>a[i];
        memset(f, 0, sizeof(f));
        f[0] = 1; f[1] = r; f[n-1]=l;
        pow_mod(f, m);
        LL ans[maxn];
        for(int i = 0; i < n; i++)
        {
            ans[i] = 0;
            for(int j = 0;j < n;j++)
                ans[i] = (ans[i]+a[j]*f[(i-j+n)%n])%mod;
        }
        cout<<ans[0];
        for(int i = 1; i < n; i++) cout<<" "<<ans[i];
        cout<<endl;
    }
    return 0;
}