行列の累乗ーフィボナッチ数列の下９桁を計算疑問点

Question

前提

入力
整数N
出力
フィボナッチ数列a1=1,a2=1,an=an-1+an-2(n>=3)の第N項aNの下９桁を出力

発生している問題・エラーメッセージ

struct Matrix {
	long long p[2][2] = { {0, 0}, {0, 0} };
};
Matrix Multiplication(Matrix A, Matrix B) { // 2×2 行列 A, B の積を返す関数
	Matrix C;

ここの構造体の所でMatrix A, Matrix B　、Matrix Cは
例えば「構造体名 オブジェクト名 = {引数1, 引数2, 引数3, ...};」のように定義されているのかなと思ったのですがその場合、「Matrix C;」はどのような立ち位置になるのでしょうか
「構造体名 オブジェクト名 = {引数1, 引数2, 引数3, ...};」のように
「Matrix Multiplication(Matrix A, Matrix B) { // 2×2 行列 A, B の積を返す関数
Matrix C;」
上記を書き直してもらえませんか

Matrix Multiplication(Matrix A, Matrix B) { // 2×2 行列 A, B の積を返す関数
	Matrix C;
	for (int i = 0; i < 2; i++) {
		for (int k = 0; k < 2; k++) {
			for (int j = 0; j < 2; j++) {
                         cout<<A.p[i][k]<<B.p[k][j]<< endl;//◆
				C.p[i][j] += A.p[i][k] * B.p[k][j];
				C.p[i][j] %= 1000000000;
			}
		}
	}
	return C;
}

cout<<A.p[i][k]<<B.p[k][j]<< endl;//◆

を入れてみたところ

入力
３
出力
11
11
11
10
11
11
01
00
22
21
11
11
12
11
11
11
55
53
33
32
35
33
23
22
3434
3421
2121
2113
2134
2121
1321
1313
15971597
....

と出ます。
具体的にこれが何を示しているのか分かりません。
ご教授お願いします。

Matrix P = A, Q

このQは何を示しているのか分かりません。

該当のソースコード

#include <iostream>
using namespace std;

struct Matrix {
	long long p[2][2] = { {0, 0}, {0, 0} };
};

Matrix Multiplication(Matrix A, Matrix B) { // 2×2 行列 A, B の積を返す関数
	Matrix C;
	for (int i = 0; i < 2; i++) {
		for (int k = 0; k < 2; k++) {
			for (int j = 0; j < 2; j++) {
				C.p[i][j] += A.p[i][k] * B.p[k][j];
				C.p[i][j] %= 1000000000;
			}
		}
	}
	return C;
}

Matrix Power(Matrix A, long long n) { // A の n 乗を返す関数
	Matrix P = A, Q; bool flag = false;
	for (int i = 0; i < 60; i++) {
		if ((n & (1LL << i)) != 0LL) {
			if (flag == false) { Q = P; flag = true; }
			else { Q = Multiplication(Q, P); }
		}
		P = Multiplication(P, P);
	}
	return Q;
}

int main() {
	// 入力 → 累乗の計算（N が 2 以上でなければ正しく動作しないので注意）
	long long N;
	cin >> N;
	Matrix A; A.p[0][0] = 1; A.p[0][1] = 1; A.p[1][0] = 1;
	Matrix B = Power(A, N - 1);

	// 出力（下から 9 桁目が 0 の場合、最初に 0 を含まない形で出力していることに注意）
	cout << (B.p[1][0] + B.p[1][1]) % 1000000000 << endl;
	return 0;
}

Comments

[episteme]

フィボナッチ数列の漸化式は行列表現できます。
本コードはこれを使ってフィボナッチ数を求めています。なにがわからんかわかりません。

https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

[episteme]

> 「Matrix C;」はどのような立ち位置になるのでしょうか

立ち位置ってなんですか?

Answer 1

ここの構造体の所でMatrix A, Matrix B　、Matrix Cは
例えば「構造体名 オブジェクト名 = {引数1, 引数2, 引数3, ...};」のように定義されているのかなと思ったのですがその場合、「Matrix C;」はどのような立ち位置になるのでしょうか

質問の意味がさっぱり分かりません。

main の中の Matrix A; A.p[0][0] = 1; A.p[0][1] = 1; A.p[1][0] = 1;
により A = {{1, 1}, {1, 0}} となっています。

main から呼び出された Power の引数でも、A = {{1, 1}, {1, 0}} です。

Multiplication の引数 A と B は、Power の中から P や Q の値で呼び出されています。

Multiplication の中の Matrix C; で C はローカル変数で、{{0, 0}, {0, 0}} と
いう初期値を持ち、その後 A と B の要素の積が足し込まれていきます。

また、「構造体名 オブジェクト名 = {引数1, 引数2, 引数3, ...};」のように書き直す
という意味は分かりません。

cout<<A.p[i][k]<<B.p[k][j]<< endl;//◆
を入れてみたところ

そんな入れ方では分かりません。次のようにしましょう。

	for (int i = 0; i < 2; i++) {
		for (int k = 0; k < 2; k++) {
			for (int j = 0; j < 2; j++) {
				C.p[i][j] += A.p[i][k] * B.p[k][j];
				C.p[i][j] %= 1000000000;
cout<<A.p[i][k] << " * " <<B.p[k][j] << " = " <<C.p[i][j] << endl;//◆
			}
		}
		cout << endl; // ★
	}

でも、forループの中でこんなにたくさん計算の途中経過を出しても無駄でしょう。
forループの後の return C; の前で、次のようにしたほうがいいのでは？

	cout << "{{" << A.p[0][0] << ", " << A.p[0][1]
		<< "}, {" << A.p[1][0] << ", " << A.p[1][1]
		<< "}}\n    * {{" << B.p[0][0] << ", " << B.p[0][1]
		<< "}, {" << B.p[1][0] << ", " << B.p[1][1]
		<< "}}\n        = {{" << C.p[0][0] << "," << C.p[0][1]
		<< "}, {" << C.p[1][0] << ", " << C.p[1][1] << "}}\n";
	return C;

Matrix P = A, Q
このQは何を示しているのか分かりません。

Matrix P = A;   // P = {{1, 1}, {1, 0}} となる
Matrix Q;       // Q = {{0, 0}, {0, 0}} となる

と同じ。

Answer 2

int Multiplication(int A, int B) { 
	int C;
        // A x B を Cに求める
	C = A * B;

	return C; // 結果を返す
}

コレ↑の int を Matrix に取り換えただけですが、なにがわかりませんか?

Comments

[jaogjig]

回答ありがとうございます。分かりました。構造体だからと違う動きになるのではないかと思っていました。ありがとうございます。

[jaogjig]

C.p[i][j] += A.p[i][k] * B.p[k][j];
ここの計算はどのようになっているのか分かりません

[episteme]

C.p[i][j] = C.p[i][j] + A.p[i][k] * B.p[k][j];

ならわかりますか?
a += b; と
a = a + b; は同じです。