直接进行迭代计算,实测用递归方式实现的话会造成超时。
#include<cstdio> int main(){ int a0, a1, a2, p, q, k; scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k); for(int i = 1; i < k; i++){ a2 = a1 * p + a0 * q; //类似斐波那契数列的迭代思想 a2 %= 10000; a0 = a1; a1 = a2; } printf("%d\n",a2); return 0; }
使用了矩阵的思想进行迭代
#include <iostream> using namespace std; struct matrix { int m[2][2]; }; matrix multiply(matrix a, matrix b) {//矩阵乘法 matrix ans; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { ans.m[i][j] = 0; for (int k = 0; k < 2; k++) ans.m[i][j] += (a.m[i][k] * b.m[k][j])%10000;//中间结果取模,否则不能通过测试 } } return ans; } matrix fastPower(matrix a, int k) {//矩阵快速幂 matrix ans; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { if (i == j) ans.m[i][j] = 1; else ans.m[i][j] = 0; } } while (k != 0) { if (k % 2 == 1) { ans = multiply(ans, a); } a = multiply(a, a); k /= 2; } return ans; } int main() { int a0, a1, p, q, k; while (cin >> a0 >> a1 >> p >> q >> k) { // 注意 while 处理多个 case // cout << a + b << endl; matrix temp; temp.m[0][0] = p; temp.m[0][1] = q; temp.m[1][0] = 1; temp.m[1][1] = 0; temp = fastPower(temp, k - 1); int ak = ((temp.m[0][0] * a1) % 10000 + (temp.m[0][1] * a0) % 10000) % 10000; cout << ak << endl; } }