結果

問題 No.314 ケンケンパ
ユーザー zeosuttzeosutt
提出日時 2015-12-08 03:12:08
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 1 ms / 1,000 ms
コード長 1,024 bytes
コンパイル時間 1,596 ms
コンパイル使用メモリ 25,040 KB
実行使用メモリ 4,372 KB
最終ジャッジ日時 2023-10-12 20:45:43
合計ジャッジ時間 2,059 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
4,368 KB
testcase_01 AC 0 ms
4,372 KB
testcase_02 AC 0 ms
4,372 KB
testcase_03 AC 1 ms
4,368 KB
testcase_04 AC 1 ms
4,372 KB
testcase_05 AC 0 ms
4,372 KB
testcase_06 AC 1 ms
4,372 KB
testcase_07 AC 1 ms
4,372 KB
testcase_08 AC 0 ms
4,372 KB
testcase_09 AC 1 ms
4,368 KB
testcase_10 AC 1 ms
4,368 KB
testcase_11 AC 0 ms
4,372 KB
testcase_12 AC 1 ms
4,372 KB
testcase_13 AC 1 ms
4,372 KB
testcase_14 AC 1 ms
4,372 KB
testcase_15 AC 0 ms
4,372 KB
testcase_16 AC 1 ms
4,372 KB
testcase_17 AC 0 ms
4,372 KB
testcase_18 AC 0 ms
4,372 KB
testcase_19 AC 1 ms
4,372 KB
権限があれば一括ダウンロードができます

ソースコード

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