20. 递推数列

题目描述

给定a0,a1,以及an=pa(n-1) + qa(n-2)中的p,q。这里n >= 2。 求第k个数对10000的模。

输入描述:

输入包括5个整数：a0、a1、p、q、k。

输出描述:

第k个数a(k)对10000的模。

示例1

输入

20 1 1 14 5

输出

8359

解法

#include <stdio.h>
#include <malloc.h>

int recursiveSeq(int a0, int a1, int p, int q, int k) {
    int *a = (int *) malloc (sizeof(int) * (k + 1));    //题目中的第 k 个表示总数的 k + 1 个，是第 0 个，第 1 个等等这么来的，需要注意，我开始弄错了，结果怎么都不一样
    a[0] = a0;
    a[1] = a1;
    for (int i = 2; i <= k; i++)
        a[i] = (p * a[i - 1] + q * a[i - 2]) % 10000;    //从一开始就模并不影响最终的值，这个可以降低数的大小，很重要
    k = a[k];
    free(a);
    return k;
}

int main() {
    for (int a0, a1, p, q, k; ~scanf("%d %d %d %d %d", &a0, &a1, &p, &q, &k);)
        printf("%d\n", recursiveSeq(a0, a1, p, q, k));
    return 0;
}