結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー hirokazu1020
提出日時 2015-04-26 23:41:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 22 ms / 5,000 ms
コード長 3,059 bytes
コンパイル時間 779 ms
コンパイル使用メモリ 86,308 KB
実行使用メモリ 7,304 KB
最終ジャッジ日時 2024-07-05 02:53:33
合計ジャッジ時間 2,041 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘Matrix<T> Matrix<T>::pow(long long int) const [with T = long long int]’:
main.cpp:45:24: warning: ‘x.Matrix<>::_col’ may be used uninitialized [-Wmaybe-uninitialized]
   45 |                 if(_row*_col!=r*c){
      |                    ~~~~^~~~~
main.cpp:91:39: note: ‘x.Matrix<>::_col’ was declared here
   91 |                 Matrix res(size,size),x(*this);
      |                                       ^

ソースコード

diff # 

#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())
#define indexOf(v,x) (find(all(v),x)-v.begin())

#define MOD 1000000007



template<class T=long long>
class Matrix{
	int _row,_col;
	T* p;
public:
	Matrix():_row(0),_col(0),p(0){}
	Matrix(int row,int col):_row(row),_col(col){
		p=new T[_row*_col];
	}
	Matrix(const Matrix& a):_row(-1),p(0){
		copy(a);
	}
	~Matrix(){
		delete[] p;
	}
	int row()const{return _row;}
	int col()const{return _col;}
	void resize(int r,int c){
		if(_row*_col!=r*c){
			delete[] p;
			p=new T[r*c];		
		}
		_row=r;
		_col=c;
	}
	void swap(Matrix& a){
		std::swap(_row,a._row);
		std::swap(_col,a._col);
		std::swap(p,a.p);
	}
	void copy(const Matrix& a){
		resize(a._row,a._col);
		for(int i=0;i<row();i++)
			for(int j=0;j<col();j++)
				p[i*col()+j]=a[i][j];
	}
	T* operator[](int i)const{return p+(i*_col);}
	Matrix& operator =(const Matrix &a){
		copy(a);
		return *this;
	}
	Matrix& operator *=(const Matrix &a){
		(*this*a).swap(*this);
		return *this;
	}
	Matrix operator *(const Matrix &a)const{
		assert(col()==a.row());
		Matrix res(row(),a.col());
		for(int i=0;i<row();i++){
			for(int j=0;j<a.col();j++)res[i][j]=0;
			for(int k=0;k<col();k++){
				T da=p[i*col()+k];
				const T * const __restrict pb=a[k];
				T * const __restrict pc=res[i];
				for(int j=0;j<a.col();j++){
					pc[j] = ((pc[j]+da*pb[j])%MOD+MOD)%MOD;
				}
			}
		}
		return res;
	}
	Matrix pow(long long n)const{
		assert(row()==col());
		int size=row();
		Matrix res(size,size),x(*this);
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++)res[i][j]=i==j;
		}
		while(n){
			if(n&1){
				(res*x).swap(res);
			}
			(x*x).swap(x);
			n>>=1;
		}
		return res;
	}
};


int F1(int n,int k,int a[]){
	int s=0;
	rep(i,n)(s+=a[i])%=MOD;
	for(int i=n;i<k;i++){
		a[i]=s;
		s=((s-a[i-n]+s)%MOD+MOD)%MOD;
	}
	return a[k-1];
}

int S1(int n,int k,int a[]){
	int s=0,ans=0;
	rep(i,n)(s+=a[i])%=MOD,(ans+=a[i])%=MOD;
	for(int i=n;i<k;i++){
		a[i]=s;
		(ans+=a[i])%=MOD;
		s=((s-a[i-n]+s)%MOD+MOD)%MOD;	
	}
	return ans;
}

int F2(int n,long long k,int a[]){
	Matrix<> mat(n,n),b(1,n);
	rep(i,n)rep(j,n)mat[i][j]=j==0||i+1==j;
	rep(i,n)b[0][i]=a[n-1-i];
	return (b*mat.pow(k-n))[0][0];
}

int S2(int n,long long k,int a[]){
	Matrix<> mat(n+1,n+1),b(1,n+1);
	rep(i,n+1)rep(j,n+1)mat[i][j]=0;
	rep(i,n)rep(j,n)mat[i][j]=j==0||i+1==j;
	rep(i,n+1)mat[i][n]=1;

	rep(i,n)b[0][i]=a[n-1-i];
	b[0][n]=0;
	int ans=0;
	rep(i,n)(ans+=a[i])%=MOD;
	ans+=(b*mat.pow(k-n))[0][n];
	return ans%MOD;
}

int a[1000000];

int main(){
	long long n,k;
	cin>>n>>k;
	rep(i,n)cin>>a[i];
	if(n<=10000&&k<=1000000)cout<<F1(n,k,a)<<' '<<S1(n,k,a)<<endl;
	else cout<<F2(n,k,a)<<' '<<S2(n,k,a)<<endl;
	return 0;
}
0