結果

問題 No.891 隣接3項間の漸化式
コンテスト
ユーザー bal4u
提出日時 2019-09-20 22:42:10
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 936 bytes
コンパイル時間 717 ms
コンパイル使用メモリ 29,952 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-14 18:42:35
合計ジャッジ時間 2,236 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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