結果

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

ソースコード

diff # 

#include<iostream>
#include<utility>
#include<vector>
using namespace std;


#define LL long long
#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define all(b) (b).begin(),(b).end()
LL A[1000001];
LL S[1000001];
LL N, K;

const LL mod =(LL) 1e9 + 7;

#define MAX_LOGN 60
template <class T>
struct Mr{
	vector<T> first;
	vector<T> C;
	vector<vector<T>> bin;
	T zero, one;
	int M;
	//n(1,,,2M)をn(1,,,M)に修正、O(M^2)
	void form(vector<T> &n){
		rev(i, M + 1, 2 * M + 1){
			reE(j, 1, M)n[i - j] = (n[i - j] + (C[M - j] * n[i]));
			n[i] = zero;
		}
	}
	//lとrを足し合わせる、O(M^2)
	void add(vector<T> &l, vector<T> &r, vector<T> &ans){
		reE(i, 1, 2 * M)ans[i] = zero;
		reE(i, 1, M)reE(j, 1, M)ans[i + j] = (ans[i + j] + (l[i] * r[j]));
		form(ans);
	}
	//初期化、O(M*MAX_LOGN)
	Mr(const vector<T>& f, const vector<T>& c, int m, T e1, T e0){
		M = m;
		first.reserve(M + 1); C.reserve(M);
		zero = e0, one = e1;
		first.push_back(zero);
		rT(i, M){ first.push_back(f[i]); C.push_back(c[i]); }
		bin.resize(MAX_LOGN);
		rT(i, MAX_LOGN)bin[i].resize(2 * M + 1);
		rE(i, 2 * M)bin[0][i] = zero; bin[0][1] = one;
		reT(i, 1, MAX_LOGN){
			add(bin[i - 1], bin[i - 1], bin[i]);
		}
	}
	//N項目の計算、戻り値がTの形であることに注意、O(M^2*logN)
	T calc(LL n){
		n--;
		vector<T> tmp, result = bin[0];
		for (int b = 0; n; b++, n >>= 1)
			if (1 & n){ tmp = result; add(tmp, bin[b], result); }
		T ans = zero;
		reE(i, 1, M)ans = ans + (result[i] * first[i]);
		return ans;
	}
};
//テンプレート、デフォルトコンストラクタのオーバーロードを忘れない
#define MOD 1000000007
struct X{
	LL val;
	X(LL  v){ val = v; }
	X(){ val = 0; }
	LL operator=(const X &another){ return val = another.val; }
	LL operator*(const X &another)const{ return (val*another.val) % MOD; }
	LL operator+(const X &another)const{ return (val + another.val) % MOD; }
};


pair<LL, LL> case1(){
	
	for (LL i= N + 1; i <= K; i++){
		A[i] = (mod + S[i - 1] - S[i - N - 1]) % mod;;
		S[i] = (A[i] + S[i - 1])%mod;
	}

	return make_pair(A[K],S[K]);
}

pair<LL, LL> case2(){
	vector<X> f((unsigned)N, 0), s((unsigned)N+1, 0), a((unsigned)N, 1), b((unsigned)N+1, 0);
	for (int i = 0; i < N; i++){
		f[i] = A[i+1];
		s[i+1] = S[i + 1];
	}
	b[(unsigned)N] = 2;
	b[0] = mod - 1;
	Mr<X> mr(f, a, (int)N, X(1), X(0));
	Mr<X> nr(s, b, (int)N + 1, X(1), X(0));

	return make_pair(mr.calc(K).val, nr.calc(K+1).val);

}

int main(void){
	cin >> N >> K;
	for (LL i = 1; i <= N; i++){
		cin >> A[i];
		S[i] = S[i - 1] + A[i];
		S[i] %= mod;
	}

	pair<LL, LL> res;
	if (K <= 1000000)res= case1();
	else res = case2();
	cout << res.first << " " << res.second << endl;
	return 0;
}
0