結果
問題 | No.314 ケンケンパ |
ユーザー |
![]() |
提出日時 | 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); | ^~~~~~~~~~~~~~~
ソースコード
#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; }