結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー hirakich1048576
提出日時 2017-04-15 15:36:32
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,116 bytes
コンパイル時間 1,705 ms
コンパイル使用メモリ 30,848 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-14 13:59:05
合計ジャッジ時間 2,625 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
typedef unsigned long long llu;
typedef   signed long long lld;
llu n;
void mtrMultiple(
    /* const */ llu* left[],
    /* const */ llu* right[],
    int sizeA,
    int sizeB,
    int sizeC,
    llu* resultVar[]){
    
    int i, j, k;
    llu resultdata[sizeA][sizeC];
    for (i = 0; i < sizeA; i++) {
        for (j = 0; j < sizeC; j++) {
            llu cell = 0;
            for (k = 0; k < sizeB; k++) {
                cell += (left[i][k] * right[k][j]) % MOD;
                cell %= MOD;
            }
            resultdata[i][j] = cell;
        }
    }
    for (i = 0; i < sizeA; i++) {
        for (j = 0; j < sizeC; j++) {
            resultVar[i][j] = resultdata[i][j];
        }
    }
}
void powmtr(/* const */ llu* mtr[], llu n, int size, llu* resultVar[]){
    int i, j;
    llu prevmtr[size][size];
    llu resultdata[size][size];
    llu* argMtr[size];
    llu* argPrm[size];
    llu* argResd[size];
    for (i = 0; i < size; i++) {
        argMtr[i] = mtr[i];
        argPrm[i] = prevmtr[i];
        argResd[i] = resultdata[i];
    }
    for (i = 0; i < size; i++) {
        for (j = 0; j < size; j++) {
            resultdata[i][j] = (i == j ? 1 : 0);
            prevmtr[i][j] = mtr[i][j];
        }
    }
    while (n) {
        if (n & 1) {
            mtrMultiple((llu**)argResd, (llu**)argPrm, size, size, size, (llu**)argResd);
        }
        n = (n >> 1);
        mtrMultiple((llu**)argPrm, (llu**)argPrm, size, size, size, (llu**)argPrm);
    }
    for (i = 0; i < size; i++) {
        for (j = 0; j < size; j++) {
            resultVar[i][j] = resultdata[i][j];
        }
    }
}
void solve(){
    int i;
    llu leftMatrix[1][2] = {
        {1, 0}
    };
    llu rightMatrix[2][2] = {
        {1, 1},
        {1, 0}
    };
    llu resultMatrix[1][2];
    llu answer;
    llu* argLeftm[1] = {leftMatrix[0]};
    llu* argRightm[2] = {rightMatrix[0], rightMatrix[1]};
    llu* argResm[1] = {resultMatrix[0]};
    powmtr((llu**)argRightm, n, 2, (llu**)argRightm);
    mtrMultiple((llu**)argLeftm, (llu**)argRightm, 1, 2, 2, (llu**)argResm);
    answer = resultMatrix[0][0] * resultMatrix[0][1] % MOD;
    printf("%llu\n", answer);
    return;
}
int main(void){
    scanf("%llu", &n);
    solve();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0