有一个整数数列 $a_0,a_1,a_2,a_3 …$
该数列的前两项 $a_0,a_1$ 的具体值已知,其它项可以通过如下递推式求出:
$a_n = p \\times a_{n-1} + q \\times a_{n-2}$($n \\ge 2$)
给定一个可能非常大的正整数 $N$ 和两个不太大的正整数 $M,K$,请你分别计算并输出 $a_{N+1},a_{N+2},\\dots,a_{N+K}$ 对 $M$ 取模的值。
输入格式
第一行包含四个正整数 $a_0,a_1,p,q$。
第二行包含一个正整数 $M$。
第三行包含一个正整数 $K$。
第四行包含一个正整数 $N$。
输出格式
输出共 $K$ 行,每行一个正整数,其中第 $i$ 行的数表示 $a_{N+i}$ 对 $M$ 取模的值。
数据范围
前三个测试点满足 $0 < a_0,a_1,p,q,M,K,N \\le 10$。
所有测试点满足 $0 < a_0,a_1,p,q \\leq 32693$,$0 < M \\leq 3 \\times 10^3$,$0 < K \\leq 10^4$,$0 < N < 10^{10^6}$。
注意,$N$ 最多有 $10^6$ 位数。
输入样例:
1 1 1 1
10
5
1
输出样例:
2
3
5
8
3
样例解释
样例其实就是斐波那契数列(即 $a_0=1,a_1=1,a_2=2,a_3=3,a_4=5,a_5=8,a_6=13…$),输出即为 $a_{2},a_{3},a_{4},a_{5},a_{6}$ 对 $10$ 取模的结果。
思路
依题意模拟,取 $n$ 的后 $7$ 位模拟(玄学,别问我)
代码
#include <iostream>
using namespace std;
const int mod = 1e7;
int a,b,p,q,m,k;
string n;
int main () {
cin >> a >> b >> p >> q >> m >> k >> n;
int x = 0;
for (char ch : n) x = (x * 10 + ch - '0') % mod;
while (x--) {
int c = (p * b + q * a) % m;
a = b,b = c;
}
while (k--) {
int c = (p * b + q * a) % m;
a = b,b = c;
cout << a << endl;
}
return 0;
}
这题不用玄学,观察到$M$不大,假设$a_i,a_{i+1}$除以$M$的余数和$a_j,a_{j+1}$相等,则$a_{j+2}$就和$a_{i+2}$一样了.因此可以找出循环节并存储”循环节中的第几位是几”.
二维数组搞一搞就行了.
确实,我明白了
数据加强了, 第8组测试数据就过不了。
我有个同学和你思路一模一样!!!
他是贺的,自己都不懂,最后居然AK