結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー 👑 CleyLCleyL
提出日時 2022-10-22 00:03:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,884 bytes
コンパイル時間 989 ms
コンパイル使用メモリ 82,136 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 08:04:17
合計ジャッジ時間 1,939 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

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

ソースコード

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

#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000007;
template <typename T>
struct mat{
vector<vector<T>> x;
int h,w;
mat():x(vector<vector<T>>()){}
mat(int h,int w):x(vector<vector<T>>(h,vector<T>(w))),h(h),w(w){}
mat(int h,int w, T c):x(vector<vector<T>>(h,vector<T>(w,c))),h(h),w(w){}
mat(vector<vector<T>> A):x(A),h(A.size()),w(A[0].size()){
}
vector<T>& operator[](int i){return x[i];}
mat& operator*=(mat& y){
mat<T> ret(h,y.w,0);
if(w != y.h){
for(int i = 0; h > i; i++){
for(int j = 0; y.w > j; j++){
ret[i][j] = -1;
}
}
}else{
for(int i = 0; h > i; i++){
for(int j = 0; y.w > j; j++){
for(int k = 0; w > k; k++){
ret[i][j] = (ret[i][j] + x[i][k]*y[k][j])%MOD;
}
}
}
}
for(int i = 0; h > i; i++){
x[i].resize(y.w);
}
w = y.w;
for(int i = 0; h > i; i++){
for(int j = 0; y.w > j; j++){
x[i][j] = ret[i][j];
}
}
return *this;
}
mat operator*(mat& y){return mat(*this) *= y;}
mat pow(long long n){//
mat<T> res(h,w);
mat<T> ret(h,w,0);
mat<T> a(h,w);
for(int i = 0; h > i; i++){
ret[i][i] = 1;
}
for(int i = 0; h > i; i++){
for(int j = 0; w > j; j++){
a[i][j] = (*this)[i][j];
}
}
while(n > 0){
if(n & 1){
ret *= a;
}
a *= a;
n/=2;
}
for(int i = 0; h > i; i++){
for(int j = 0; w > j; j++){
res[i][j] = ret[i][j];
}
}
return res;
}
};
int main(){
vector<vector<long long>> x{{1,2,1,1},{1,0,0,0},{0,2,1,1},{0,0,1,0}};
vector<vector<long long>> y{{1},{0},{1},{0}};
mat<long long> A(x);
mat<long long> B(y);
long long n;cin>>n;
auto C = A.pow(n-1)*B;
cout << C[0][0] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0