Fork me on GitHub

[UVa-10870] Recurrences(矩阵构造与快速幂)

发表于 | 分类于
字数统计: 766字 | 阅读时长 ≈ 4分钟

题面

传送门:UVa-10870
题目大意:给出F(n)的递推式,求出F(n)%m的值。

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, defined 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 coefficients: 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 file contains several test cases. Each test case begins with three integers: d, n, m, followed bytwo sets of d non-negative integers. The first set contains coefficients: a1, a2, . . . , ad. The second set gives values of f(1), f(2), . . . , f(d).
You can assume that: 1 ≤ d ≤ 15, 1 ≤ n ≤ 2^31-1，1 ≤ m ≤ 46340. All numbers in the input will fit 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
2
1
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)递推到f(n+1)就可以使矩阵快速幂了
比如当d=5时,不难写出这样的矩阵乘法

同理d为任意值时都可以写出这样的矩阵乘法。

这样我们就可以定义一个常数矩阵A,在从f(n)递推到f(n+1)乘以A即可,我们已经知道了f(1)到f(d)的值

从f(d)到f(n)一共要乘以A （n-d）次

一个矩阵快速幂即可其中快速幂的复杂度为logn,矩阵的复杂度为d^3(没有优化的话)

因此时间复杂度为

这便是正解了。qwq

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL d,m,f[26];
struct node{LL a[16][16];};

node multi(node x,node y)
{
    node t;
    memset(t.a,0,sizeof(t.a));
    for(int i = 1; i <= d; i++)
    {
        for(int j = 1; j <= d; j++)
        {
            for(int k = 1; k <= d; k++)
                t.a[i][j] = (t.a[i][j]+x.a[i][k]*y.a[k][j])%m;
        }
    }
    return t;
}
LL find(LL n,node sa)
{
    node t;
    memset(t.a,0,sizeof(t.a));
    for(int i=1; i<=d; i++)  t.a[i][i]=1;
    while(n)
    {
        if(n&1) t=multi(t,sa);
        sa=multi(sa,sa);
        n>>=1;
    }
    LL ans=0;
    for(int i=1;i<=d;i++)
        ans=(ans+t.a[1][i]*f[i])%m;
    return ans;
}
int main(int argc, char *argv[])
{
    LL n;
    node sa;
    while(scanf("%lld%lld%lld",&d,&n,&m) == 3 &&d)
    {
        memset(sa.a,0,sizeof(sa.a));
        for(int i=1; i<=d; i++)
            scanf("%d",&sa.a[1][i]);
        for(int i=d; i>=1; i--)
            scanf("%d",&f[i]);
        for(int i=2; i<=d; i++)
            sa.a[i][i-1]=1;
        if(n<=d) printf("%lld\n",f[d-n+1]%m);
        else
            printf("%lld\n",find(n-d,sa));
    }
    return 0;
}