結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0