[原创]FZU 1692 [循环矩阵+矩阵快速幂]【数论】

2016-10-22 16:58:05 Tabris_ 阅读数：316

博客爬取于2020-06-14 22:43:02
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52893406

题目链接：http://acm.fzu.edu.cn/problem.php?pid=1692
----------------------------------------.
Problem 1692 Key problem
Accept: 197 Submit: 865
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

Whenever rxw meets Coral, he requires her to give him the laboratory key. Coral does not want to give him the key, so Coral ask him one question. if rxw can solve the problem, she will give him the key, otherwise do not give him. rxw turns to you for help now,can you help him?
N children form a circle, numbered 0,1,2, … …, n-1,with Clockwise. Initially the ith child has Ai apples. Each round game, the ith child will obtain ( LA(i+n-1)%n+RA(i+1)%n ) apples. After m rounds game, Coral would like to know the number of apples each child has. Because the final figure may be very large, so output the number model M.
Input

The first line of input is an integer T representing the number of test cases to follow. Each case consists of two lines of input: the first line contains five integers n,m,L,R and M . the second line contains n integers A0, A1, A2 … An-1. (0 <= Ai <= 1000,3 <= n <= 100,0 <= L, R <= 1000,1 <= M <= 10 ^ 6,0 <=m < = 10 ^ 9). After m rounds game, output the number model M of apples each child has.
Output

Each case separated by a space. See sample.
Sample Input

1
3 2 3 4 10000
1 2 3
Sample Output

120 133 131
Source

FOJ月赛-2009年3月— Coral
----------------------------------------.

题目大意：就是每个人初始有a[i]个苹果,每一轮能得到左边L倍+右边R倍的苹果,问你M轮之后每个人有多少个苹果.

解题思路:
很明显的矩阵快速幂.构造矩阵非常简单
但是要注意下n≤100 所以n^3会超时,所以要优化一下,
根据矩阵我们能够发现
[1 L 0 0 R]
[R 1 L 0 0]
[0 R 1 L 0]
[0 0 R 1 L]
[L 0 0 R 1]

这是一个很明显的循环矩阵
根据循环矩阵的n次幂还是循环矩阵的这个性质我们每次求解的时候只需要求解一行或一列就可以了，这样的话就能把n^3优化到n^2了
这样就不会超时了

附本题代码
---------------------------------。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//#include <bits/stdc++.h>
# include <stdio.h>
# include <iostream>
# include <algorithm>
# include <string.h>

using namespace std;

# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) (a)>0?(a):-(a)
# define min(a,b) (a)>(b)?(a):(b)
# define lalal puts("*******");
typedef long long int LL ;
/*******************************/

const int N = 100+5;
int MOD ;

struct Matrix
{
    LL m[N][N];
    int row,culumn;
    void clearE()
    {
        for(int i=0; i<row; i++)
            for(int j=0; j<culumn; j++)
                m[i][j]=(i==j);
    }
    void clearO()
    {
        for(int i=0; i<row; i++)
            for(int j=0; j<culumn; j++)
                m[i][j]=0;
    }
    void display()
    {
        for(int i=0; i<row; i++)
        {
            for(int j=0; j<culumn; j++)
                printf("%d ",m[i][j]);
            puts("");
        }
    }
};
//循环矩阵的写法。。对于循环矩阵来说 行和列是一样都循环的
Matrix operator *(Matrix &a,Matrix &b)
{
    Matrix c;
    c.row=a.row,c.culumn=b.culumn,c.clearO();

    for (int k = 0; k < a.culumn; k++)
        if (a.m[0][k])
        {
            for (int j = 0; j < b.culumn; j++)
                if (b.m[k][j])
                    c.m[0][j] = (c.m[0][j] + a.m[0][k] * b.m[k][j]) % MOD;
        }
    for (int i = 1; i < c.culumn; i++)  //每一次根据规律把矩阵打出来
    {
        c.m[i][0] = c.m[i - 1][c.culumn - 1];
        for (int j = 1; j < c.culumn; j++)
            c.m[i][j] = c.m[i - 1][j - 1];
    }
    return c;
}

Matrix operator ^(Matrix &a,int b)
{
    Matrix c;
    c.row=a.row,c.culumn=a.culumn,c.clearE();

    while(b)
    {
        if(b&1) c=c*a;
        b>>=1;
        a=a*a;
    }

    return c;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n,m,L,R,M;
        scanf("%I64d%I64d%I64d%I64d%I64d",&n,&m,&L,&R,&M);

        MOD=M;
        Matrix a,b;
        a.row=1,b.row=a.culumn=b.culumn=n,a.clearO(),b.clearO();

        for(int i=0; i<n; i++)
        {
            scanf("%I64d",&a.m[0][i]);
            a.m[0][i]%=MOD;
            b.m[(i-1+n)%n][i]=R%MOD;
            b.m[(i+1)%n][i]=L%MOD;
            b.m[i][i]=1;
        }

        b=b^(m);
        a=a*b;

        for(int i=0; i<n; i++)
        {
            if(i)printf(" ");
            printf("%I64d",a.m[0][i]);
        }
        puts("");
    }
    return 0;
}