51 nod 1126は、n番目の行列の迅速なべき乗を求める.
4492 ワード
タイトル:
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1126
件名:
f(1)=1、f(2)=1、f(n)=(A*f(n−1)+B*f(n−2))mod 7と定義され、A、B、N、f(n)の値を与えるシーケンスがある.Inputは3つの数を入力します.A、B、N.数字の間をスペースで区切る.(-10000<=A、B<=10000、1<=N==10^9)Output出力f(n)の値です.
考え方
マトリクスの素早いべき乗問題は、まず2*2の行列を作ります.行列要素は左から右へそれぞれa 1 b 0です.この行列のn-2乗を求めて、1*2の行列を作ります.要素はそれぞれf(2)f(1)です.この行列を前に求めたべき乗と乗算して、得られた結果の最初の列の要素が答えです.
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1126
件名:
f(1)=1、f(2)=1、f(n)=(A*f(n−1)+B*f(n−2))mod 7と定義され、A、B、N、f(n)の値を与えるシーケンスがある.Inputは3つの数を入力します.A、B、N.数字の間をスペースで区切る.(-10000<=A、B<=10000、1<=N==10^9)Output出力f(n)の値です.
考え方
マトリクスの素早いべき乗問題は、まず2*2の行列を作ります.行列要素は左から右へそれぞれa 1 b 0です.この行列のn-2乗を求めて、1*2の行列を作ります.要素はそれぞれf(2)f(1)です.この行列を前に求めたべき乗と乗算して、得られた結果の最初の列の要素が答えです.
#include
using namespace std;
const int N = 10 + 10, MOD = 7;
struct matrix
{
int row, col;
int mat[N][N];
matrix(int _row=0, int _col=0)
{
init(_row, _col);
}
void init(int _row, int _col)
{
row = _row, col = _col;
memset(mat, 0, sizeof mat);
}
matrix operator* (matrix b)
{
matrix c(row, b.col);
for(int i = 1; i <= row; i++)
for(int j = 1; j <= b.col; j++)
for(int k = 1; k <= col; k++)
c.mat[i][j] = (c.mat[i][j] + mat[i][k] * b.mat[k][j] % MOD + MOD) % MOD;
return c;
}
};
matrix matrix_pow(matrix a, int b)
{
matrix ans(a.row, a.col);
ans.mat[1][1] = ans.mat[2][2] = 1;
while(b)
{
if(b & 1) ans = ans * a;
b >>= 1;
a = a * a;
}
return ans;
}
int main()
{
int a, b, n;
scanf("%d%d%d", &a, &b, &n);
if(n <= 2) printf("%d
", 1);
else
{
matrix arr(2, 2);
arr.mat[1][1] = a, arr.mat[2][1] = b;
arr.mat[1][2] = 1, arr.mat[2][2] = 0;
matrix brr(1, 2);
brr.mat[1][1] = 1, brr.mat[1][2] = 1;
arr = matrix_pow(arr, n - 2);
brr = brr * arr;
printf("%d
", brr.mat[1][1]);
}
return 0;
}