結果

問題 No.891 隣接3項間の漸化式
コンテスト
ユーザー bal4u
提出日時 2019-09-20 22:42:10
言語 C(gnu17)
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -std=gnu17 -Wno-error=implicit-function-declaration -Wno-error=implicit-int -Wno-error=incompatible-pointer-types -Wno-error=int-conversion -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 936 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 187 ms
コンパイル使用メモリ 39,620 KB
最終ジャッジ日時 2026-02-22 04:44:01
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// yukicoder 891 隣接3項間の漸化式
// 2019.9.20 bal4u

#include <stdio.h>
#include <string.h>

typedef long long ll;

#define MOD 1000000007
#define SZ 2
#define MSZ (sizeof(com))
int com[SZ][SZ], a[SZ][SZ];

void mat_mul(int ab[SZ][SZ], int a[SZ][SZ], int b[SZ][SZ], int n) {
	int i, r, c;
	
	memset(ab, 0, MSZ);
	for (r = 0; r < n; r++) for (i = 0; i < n; i++) for (c = 0; c < n; c++)
		ab[r][c] = (ab[r][c] + (ll)a[r][i] * b[i][c]) % MOD;
}

void mat_pow(int ap[SZ][SZ], int a[SZ][SZ], int n, int p) {
	int i, tmp[SZ][SZ];
	
	memset(ap, 0, MSZ);
	for (i = 0; i < n; i++) ap[i][i] = 1;
	while (p > 0) {
		if (p & 1) mat_mul(tmp, ap, a, n), memcpy(ap, tmp, MSZ);
		mat_mul(tmp, a, a, n), memcpy(a, tmp, MSZ);
		p >>= 1;
	}
}

int main()
{
	int x, y, n;
	
	scanf("%d%d%d", &x, &y, &n);
	a[0][0] = x, a[0][1] = y;
	a[1][0] = 1, a[1][1] = 0;
	mat_pow(com, a, 2, n);  // 行列のべき乗
	printf("%d\n", com[1][0]);
	return 0;
}
0