結果

問題 No.314 ケンケンパ
コンテスト
ユーザー zeosutt
提出日時 2015-12-08 03:12:08
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 1 ms / 1,000 ms
コード長 1,024 bytes
コンパイル時間 887 ms
コンパイル使用メモリ 21,888 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-14 19:05:37
合計ジャッジ時間 1,778 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:50:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |         scanf("%d", &n);
      |         ^~~~~~~~~~~~~~~

ソースコード

diff # 

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

#define MAT_ORDER 3
#define MOD 1000000007

typedef long long sqmat_t[MAT_ORDER][MAT_ORDER];

void multiSqMat(sqmat_t Z, const sqmat_t X, const sqmat_t Y) {
	int i, j, k;
	for (i = 0; i < MAT_ORDER; i++)
		for (j = 0; j < MAT_ORDER; j++) {
			Z[i][j] = 0;
			for (k = 0; k < MAT_ORDER; k++) {
				Z[i][j] += X[i][k] * Y[k][j];
				Z[i][j] %= MOD;
			}
		}
}

void fastPowMat(sqmat_t Y, const sqmat_t X, long long n) {
	int i;
	sqmat_t tmp;
	sqmat_t XX, prod = {0};

	memcpy(XX, X, sizeof(sqmat_t));
	for (i = 0; i < MAT_ORDER; i++)
		prod[i][i] = 1;

	while (n) {
		if (n & 1) {
			multiSqMat(tmp, prod, XX);
			memcpy(prod, tmp, sizeof(sqmat_t));
		}

		multiSqMat(tmp, XX, XX);
		memcpy(XX, tmp, sizeof(sqmat_t));

		n >>= 1;
	}

	memcpy(Y, prod, sizeof(sqmat_t));
}

int main(void) {
	int n;
	sqmat_t tmp;
	const sqmat_t Q = {{0, 1, 0}, {0, 0, 1}, {1, 1, 0}};

	scanf("%d", &n);

	fastPowMat(tmp, Q, n);

	printf("%lld\n", (tmp[0][2] + tmp[1][2] + tmp[2][2]) % MOD);

	return 0;
}
0