結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
コンテスト
ユーザー suikameron1
提出日時 2019-06-10 17:17:45
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 3,375 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,145 ms
コンパイル使用メモリ 106,880 KB
実行使用メモリ 18,816 KB
最終ジャッジ日時 2024-10-06 00:43:17
合計ジャッジ時間 2,411 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
raw source code 

using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		long n = long.Parse(Console.ReadLine());
    long mod = 1000000007;
    long[,] multipleMatrix = new long[,]
    {
      {1,1},
      {1,0}
    };
    long[,] firstMatrix = new long[,]
    {
      {1},
      {1}
    };

    long[,] subMatrix = MatrixProductRepeat(multipleMatrix,n-1,mod);
    long[,] answerMatrix = MatrixProduct(subMatrix,firstMatrix,mod);
    Console.WriteLine((answerMatrix[0,0]*answerMatrix[1,0])%mod);
	}

  static long[,] MatrixProductRepeat(long[,] originalMatrix, long mul, long p)
  {//平方行列のmul乗(mod p)を返す
  //ただし、mod=0でそのまま返す
    long matrixLength = originalMatrix.GetLength(0);
    long[,] answerMat = new long[matrixLength,matrixLength];//配列は、=引数とせずnewとしないと引数元も変更される
    for(int i = 0; i < matrixLength; i++)
    {
      for(int j = 0; j < matrixLength; j++)
      {
        answerMat[i,j] = originalMatrix[i,j];
      }
    }
    List<int> multipleList = new List<int>();//0は元の行列、1は積の行列をかける

    long memo = mul;
    while(memo > 1)
    {
      if(memo % 2 == 1)
      {
        multipleList.Add(0);
        memo--;
      }else
      {
        multipleList.Add(1);
        memo /= 2;
      }
    }

    for(int i = multipleList.Count()-1; i >= 0; i--)
    {
      if(multipleList[i] == 0) answerMat = MatrixProduct(answerMat,originalMatrix,p);
      else answerMat = MatrixProduct(answerMat,answerMat,p);
    }

    if(mul == 0)//0乗では単位行列を返す
    {
      for(int i = 0; i < matrixLength; i++)
      {
        for(int j = 0; j < matrixLength; j++)
        {
          if(i == j) answerMat[i,j] = 1;
          else answerMat[i,j] = 0;
        }
      }
    }
    
    return answerMat;
  }

  static long[,] MatrixProduct(long[,] originalMatrixA, long[,] originalMatrixB, long p)
  //行列の積(mod p)を返す
  //ただし、p=0でそのまま返す
  {
    long matrixLengthH = originalMatrixA.GetLength(0);
    long matrixLengthW = originalMatrixB.GetLength(1);
    long matrixLengthSub = originalMatrixA.GetLength(1);
    if(originalMatrixA.GetLength(1) == originalMatrixB.GetLength(0))//これを満たさないと行列計算は不可能
    {
      matrixLengthSub = originalMatrixA.GetLength(1);
    }

    if(p != 0)
    {
      for(int i = 0; i < originalMatrixA.GetLength(0); i++)
      {
        for(int j = 0; j < originalMatrixA.GetLength(1); j++)
        {
          originalMatrixA[i,j] %= p;
        }
      }
      for(int i = 0; i < originalMatrixB.GetLength(0); i++)
      {
        for(int j = 0; j < originalMatrixB.GetLength(1); j++)
        {
          originalMatrixB[i,j] %= p;
        }
      }
    }
    
    long[,] answerM = new long[matrixLengthH, matrixLengthW];
    
    for(long lineM = 0; lineM < matrixLengthH; lineM++)
    {
      for(long rowM = 0; rowM < matrixLengthW; rowM++)
      {
        long ansMemo = 0;
        for(long i = 0; i < matrixLengthSub; i++)
        {
          ansMemo += originalMatrixA[lineM,i] * originalMatrixB[i,rowM];//成分計算
          if(p != 0) ansMemo %= p;
        }
        answerM[lineM,rowM] = ansMemo;
      }
    }
    return answerM;
  }
  
}
0