Another kind of Fibonacci
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 115 Accepted Submission(s): 50
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 231 – 1
X : 2<= X <= 231– 1
Y : 2<= Y <= 231 – 1
2 1 1 3 2 3
6 196
１ １
１ １ ０
０ １ １
１ １ ０ ０
０ １ １ ０
０ １ １ １
１ １ １
０ ０ １
１ １ １ ０ ０
０ ０ １ ０ ０
０ １ ０ １ ０
０ １ ０ １ １
1 p 1 0 0
0 0 1 0 0
0 r 0 1 0
0 s 0 1 1
我们可以根据(s[n-2], a[n-1]^2, a[n-1]*a[n-2], a[n-2]^2) * A = (s[n-1], a[n]^2, a[n]*a[n-1], a[n-1]^2)
能够求出关系矩阵
|1 0 0 0 |
A = |1 x^2 x 1 |
|0 2*x*y y 0 |
|0 y^2 0 0 |
这样就A了！
#include <cstdio>
#include <cstring>
#include<iostream>
#include <algorithm>
using namespace std;
#define MOD 10007
struct Matrix
{
int numbers[4][4];
Matrix(int x = 0, int y = 0)
{
memset(numbers, 0, 4 * 4 * sizeof(int));
numbers[0][0] = numbers[0][1] = 1;
numbers[1][1] = x * x % MOD; numbers[1][2] = y * y % MOD; numbers[1][3] = 2 * x * y % MOD;
numbers[2][1] = 1;
numbers[3][1] = x; numbers[3][3] = y;
}
Matrix(bool flag)
{
memset(numbers, 0, 4 * 4 * sizeof(int));
numbers[0][0] = 1;
numbers[1][1] = 1;
numbers[2][2] = 1;
numbers[3][3] = 1;
}
};
Matrix operator * (const Matrix& lh, const Matrix& rh)
{
Matrix temp;
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j)
{
int sum = 0;
for (int k = 0; k < 4; ++k)
sum = (sum + lh.numbers[i][k] * rh.numbers[k][j]) % MOD;
temp.numbers[i][j] = sum;
}
return temp;
}
int main()
{
int n, x, y;
while (scanf("%u%u%u", &n, &x, &y) != EOF)
{
Matrix mat(x % MOD, y % MOD), res(true);
for (; n > 0; n >>= 1)
{
if (n & 1)
res = mat * res;
mat = mat * mat;
}
int sum = 0;
for (int i = 0; i < 4; ++i)
sum = (sum + res.numbers[0][i]) % MOD;
printf("%u/n", sum);
}
return 0;
}