[UVA][費式延伸 矩陣 D&C] 10689 - Yet another Number Sequence
Problem B
Yet another Number Sequence
Input: standard input
Output: standard output
Time Limit: 3 seconds
Let's define another number sequence, given by the following function:
f(0) = af(1) = bf(n) = f(n-1) + f(n-2), n > 1
When a = 0 and b = 1, this sequence gives the Fibonacci Sequence. Changing the values of a and b , you can get many different sequences. Given the values of a, b, you have to find the last m digits of f(n) .
Input
The first line gives the number of test cases, which is less than 10001. Each test case consists of a single line containing the integers a b n m. The values of a and b range in [0,100], value of n ranges in [0, 1000000000] and value of m ranges in [1, 4].
Output
For each test case, print the last m digits of f(n). However, you should NOT print any leading zero.
Sample Input Output for Sample Input
40 1 11 30 1 42 40 1 22 40 1 21 4
|
8942967711
946 |
轉換成第 0 項被加了幾次, 第 1 項被加了幾次, 中間計算用 D&C 解決
#include <math.h>
struct M {
int v[2][2];
} I = {1,0,0,1}, o = {0,0,0,0}, A = {1,1,1,0};
void mult(M &a, M &b, int m) {
static int i, j, k;
M t = o;
for(i = 0; i < 2; i++) {
for(j = 0; j < 2; j++) {
for(k = 0; k < 2; k++) {
t.v[i][j] += a.v[i][k]*b.v[k][j];
t.v[i][j] %= m;
}
}
}
a = t;
}
M calc(int n, int m) {
M x = I, y = A;
while(n) {
if(n&1) mult(x, y, m);
mult(y, y, m);
n /= 2;
}
return x;
}
int main() {
int n, m, a, b, t;
scanf("%d", &t);
while(t--) {
scanf("%d %d %d %d", &a, &b, &n, &m);
m = (int)pow(10, m);
M res = calc(n, m);
int ans = res.v[1][0]*b+res.v[1][1]*a;
printf("%d\n", ans%m);
}
return 0;
}