結果

問題 No.3228 Very Large Fibonacci Sum
コンテスト
ユーザー ジュ・ビオレ・グレイス
提出日時 2025-07-20 02:08:17
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 989 bytes
コンパイル時間 902 ms
コンパイル使用メモリ 86,944 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-20 02:08:59
合計ジャッジ時間 2,762 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.algorithm, std.array, std.conv, std.typecons;

immutable p = 1000000007L;

void main() {
	auto tmp = readln.split.to!(long[]),
	a = tmp[0], b = tmp[1], c = tmp[2], d = tmp[3], e = tmp[4], N = tmp[5];
	
	Matrix A;
	A[0][0] = (c+1)%p, A[0][1] = (d-c)%p, A[0][2] = (-d)%p, A[0][3] = e%p,
	A[1][0] = 1,
	                   A[2][1] = 1,
	                                                        A[3][3] = 1;
	
	Matrix M;
	M[0][0] = M[1][1] = M[2][2] = M[3][3] = 1;
	auto power = 1L;
	while (power <= N) {
		if ((N & power) != 0) M = multiply(A, M);
		A = multiply(A, A);
		power *= 2;
	}
	
	auto mod = (M[2][0]*(a*(d+1)%p + b*(c+1)%p + e)%p + M[2][1]*(a+b)%p + M[2][2]*a%p + M[2][3]) % p;
	writeln(mod < 0 ? mod + p : mod);
}

// 0 1 2
// 3 4 5
// 6 7 8
alias Matrix = long[4][4];

Matrix multiply(Matrix a, Matrix b) {
	Matrix c;
	foreach (i; 0 .. 4) foreach (j; 0 .. 4) {
		foreach (k; 0 .. 4) {
			c[i][j] += (a[i][k] * b[k][j]) % p;
			c[i][j] %= p;
		}
	}
	return c;
}
0