結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー kyuridenamidakyuridenamida
提出日時 2015-04-26 23:21:42
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 131 ms / 5,000 ms
コード長 4,001 bytes
コンパイル時間 1,747 ms
コンパイル使用メモリ 157,856 KB
実行使用メモリ 10,832 KB
最終ジャッジ日時 2023-09-18 09:56:05
合計ジャッジ時間 5,305 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 131 ms
4,704 KB
testcase_03 AC 11 ms
4,376 KB
testcase_04 AC 48 ms
4,380 KB
testcase_05 AC 38 ms
4,376 KB
testcase_06 AC 47 ms
4,376 KB
testcase_07 AC 80 ms
4,380 KB
testcase_08 AC 8 ms
4,376 KB
testcase_09 AC 60 ms
4,376 KB
testcase_10 AC 21 ms
4,376 KB
testcase_11 AC 23 ms
4,376 KB
testcase_12 AC 39 ms
4,380 KB
testcase_13 AC 14 ms
4,376 KB
testcase_14 AC 4 ms
4,380 KB
testcase_15 AC 101 ms
4,532 KB
testcase_16 AC 82 ms
4,380 KB
testcase_17 AC 21 ms
4,380 KB
testcase_18 AC 88 ms
4,380 KB
testcase_19 AC 123 ms
4,920 KB
testcase_20 AC 109 ms
10,732 KB
testcase_21 AC 112 ms
10,684 KB
testcase_22 AC 108 ms
10,832 KB
testcase_23 AC 6 ms
4,376 KB
testcase_24 AC 51 ms
6,600 KB
testcase_25 AC 47 ms
6,376 KB
testcase_26 AC 44 ms
6,140 KB
testcase_27 AC 59 ms
7,192 KB
testcase_28 AC 13 ms
4,376 KB
testcase_29 AC 101 ms
10,344 KB
testcase_30 AC 126 ms
4,700 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 34 ms
4,380 KB
testcase_33 AC 52 ms
4,376 KB
testcase_34 AC 42 ms
4,376 KB
testcase_35 AC 34 ms
4,380 KB
testcase_36 AC 94 ms
4,392 KB
testcase_37 AC 8 ms
4,380 KB
testcase_38 AC 108 ms
4,504 KB
testcase_39 AC 40 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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