每日一九度之 题目1081：递推数列
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：6966
解决：978
给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。 求第k个数对10000的模。
</dd> </dl> <dl> <dt> 输入： </dt> <dd>输入包括5个整数：a0、a1、p、q、k。
第k个数a(k)对10000的模。
</dd> </dl> <dl> <dt> 样例输入： </dt> <dd>20 1 1 14 5</dd> </dl> <dl> <dt> 样例输出： </dt> <dd>
8359</dd> </dl>
普通方法（时间超限），当数据比较小的时候适用，数据大了就会产生时间超限的问题：
//Asimple #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <cctype> #include <cstdlib> #include <stack> #include <cmath> #include <set> #include <map> #include <string> #include <queue> #include <limits.h> #define INF 0x7fffffff using namespace std; const int maxn = 1005; const int mod = 10000; typedef long long ll; int a[maxn]; int a0, a1, p, q, k; int main(){ while( ~scanf("%d %d %d %d %d",&a0, &a1, &p, &q, &k) ){ a[0] = a0%mod; a[1] = a1%mod; for(int i=2; i<=k; i++){ a[i] = (p*a[i-1]%mod + q*a[i-2]%mod)%mod; } printf("%d\n",a[k]); } return 0; }
而将题目转化成矩阵的快速幂计算将会剩下很多时间，但是需要对矩阵的运算需要有一定的了解。
详见：http://blog.csdn.net/lhyer/article/details/47841763
#include <stdio.h> #include <stdlib.h> #define MOD 10000 //结果取MOD，避免高精度运算 /*将矩阵p与矩阵q相乘，结果存入p矩阵*/ void Matrix_mul(int p[2][2], int q[2][2]) { int i, j, k; int t[2][2]={0}; for(i = 0; i <= 1; i++) for(j = 0; j <= 1; j++) for(k = 0; k <= 1; k++) t[i][j] += p[i][k] * q[k][j]; for(i = 0; i <= 1; i++) for(j = 0; j <= 1; j++) p[i][j] = t[i][j] % MOD; } /*计算p矩阵的n次方，结果存入p矩阵*/ void Matrix_cal(int p[2][2], int n) { int i, j; int t[2][2]; for(i = 0; i <= 1; i++) for(j = 0; j <= 1; j++) t[i][j] = p[i][j]; if(n == 1) return; else if(n & 1) { Matrix_cal(p, n-1); Matrix_mul(p, t); } else { Matrix_cal(p, n/2); Matrix_mul(p, p); } } int main() { int a0, a1, p, q, k; while(scanf("%d%d%d%d%d", &a0, &a1, &p, &q, &k) != EOF) { if(k == 0) printf("%d\n", a0); else if(k == 1) printf("%d\n", a1); else { int matrix[2][2] = { {p%MOD, q%MOD}, {1, 0} }; Matrix_cal(matrix, k-1); printf("%d\n", (a1 * matrix[0][0] + a0 * matrix[0][1]) % MOD); } } return 0; }
