結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー kyuridenamida
提出日時 2015-04-26 23:21:42
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 130 ms / 5,000 ms
コード長 4,001 bytes
コンパイル時間 1,556 ms
コンパイル使用メモリ 171,168 KB
実行使用メモリ 11,092 KB
最終ジャッジ日時 2024-07-05 01:38:08
合計ジャッジ時間 4,741 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long

long long gcd(long long a,long long b){
	return b ? gcd(b,a%b) : a;
}
long long lcm(long long a,long long b){
	return a / gcd(a,b) * b;
}

long long mul(long long a,long long b,const long long mod){
	return b?(mul(a*2,b/2,mod)+(b&1?a:0))%mod:0;
}

long long bpow(long long a,long long b,const long long mod){
	return (b?bpow(a*a%mod,b/2,mod)*(b&1?a:1):1)%mod;
}

long long inv(long long a,const long long mod){
	return bpow(a,mod-2,mod);
}

// to overflow
/*long long bpow(long long a,long long b,const long long mod){
	return (b?mul(bpow(mul(a,a,mod),b/2,mod),(b&1?a:1),mod):1)%mod;
}*/
class mInt{
public:
	static const long long mod = 1000000007;
	long long v;
	mInt():v(0){}
	mInt(long long v):v((v%mod+mod)%mod){}
};
mInt& operator += (mInt &a,mInt b){ return a = a.v + b.v; }
mInt& operator -= (mInt &a,mInt b){ return a = a.v - b.v; }
mInt& operator *= (mInt &a,mInt b){ return a = a.v * b.v; }
mInt& operator /= (mInt &a,mInt b){ return a = a.v * inv(b.v,mInt::mod); }
mInt operator + (mInt a,mInt b){ return a += b; }
mInt operator - (mInt a,mInt b){ return a -= b; }
mInt operator * (mInt a,mInt b){ return a *= b; }
mInt operator / (mInt a,mInt b){ return a /= b; }
ostream& operator<<(ostream& os, const mInt& x){ return os << x.v; }

typedef mInt number;
const number eps = 0;
typedef vector<number> Array;
typedef vector<Array> matrix;

// O( n )
matrix identity(int n) {
  matrix A(n, Array(n));
  for (int i = 0; i < n; ++i) A[i][i] = 1;
  return A;
}
// O( n^2 )
Array mul(const matrix &A, const Array &x) {
  Array y(A.size());
  for (int i = 0; i < A.size(); ++i)
    for (int j = 0; j < A[0].size(); ++j)
      y[i] = A[i][j] * x[j];
  return y;
}
// O( n^3 )
matrix mul(const matrix &A, const matrix &B) {
  matrix C(A.size(), Array(B[0].size()));
  for (int i = 0; i < C.size(); ++i)
    for (int j = 0; j < C[i].size(); ++j)
      for (int k = 0; k < A[i].size(); ++k)
        C[i][j] += A[i][k] * B[k][j];
  return C;
}
// O( n^3 log e )
matrix pow(const matrix &A, int e) {
  return e == 0 ? identity(A.size())  :
     e % 2 == 0 ? pow(mul(A, A), e/2) : mul(A, pow(A, e-1));
}
#define DIV (1000000007)
class BIT : public vector<int>{
public:
	BIT(int n){ resize(n+1); fill(begin(),end(),0); };
	int operator()(int i){
		i++;
		int ans = 0;
		while(i > 0){
			ans = ( ans + (*this)[i] ) % DIV;
			i -= i & -i;
		}
		return ans;
	}
	int operator()(int s,int t){
		return ( ( (*this)(t) - (*this)(s-1) ) % DIV + DIV ) % DIV;
	}
	void add(int i,int x){
		i++;
		int ans = 0;
		while( i < size() ){
			(*this)[i] = ( (*this)[i] + x ) % DIV;
			i += i & -i;
		}
	}
	void change(int i,int x){
		add(i,-(*this)(i,i));
		add(i,x);
	}
};


signed main(){
	long long sum = 0;
	long long N,K;
	cin >> N >> K;
	if(K <= 1000000){
		BIT seg(K+10);
		for(int i = 1 ; i <= N ; i++){
			int w;
			cin >> w;
			seg.add(i,w);
		}
		
		for(int i = N+1 ; i <= K ; i++)
			seg.add(i,seg(i-N,i));
		
		cout << seg(K,K) << " " << seg(K) << endl;
	}else{
		matrix A(N,Array(N));
		Array B(N);
		for(int i = 1 ; i <= N ; i++){
			int w;
			cin >> w;
			B[i-1] = w;
		}
		for(int i = 0 ; i < N ; i++){
			for(int j = 0 ; j < N ; j++){
				if( i == 0 ) A[i][j] = 1;
				else A[i][j] = i == j+1; 
			}
		}
		
		int M = K - N;
		
		auto m = pow(A,M);
		mInt sum = 0;
		for(int j = 0 ; j < N ; j++){
			sum += m[0][j] * B[N-j-1];
		}
		
		
		mInt res = 0;
		//for(int i = 0 ; i+1 < N ; i++)
		//	res += B[i];
		
		matrix S(2*N,Array(2*N));
		for(int i = 0 ; i < N ; i++){
			for(int j = 0 ; j < N ; j++){
				S[i][j] = A[i][j];
			}
		}
		for(int i = 0 ; i < N ; i++){
			S[i+N][i] = 1;
		}
		for(int i = 0 ; i < N ; i++){
			S[i+N][i+N] = 1;
		}
		S = pow(S,M+1);
		for(int i = 0 ; i < N ; i++){
			for(int j = 0 ; j < N ; j++)
				A[i][j] = S[i+N][j];
		}
		for(int j = 0 ; j < N ; j++){
			res += j+1 < N ? B[j] : 0;
			res += A[0][j] * B[N-j-1];
		}
		cout << sum << " " << res << endl;
		//cout << mul(pow(A,K-1),B) << endl;
		
	}
	
}
0