#22573 (C++11) No.194 フィボナッチ数列の理解(1)

提出ソース

結果

問題	No.194 フィボナッチ数列の理解(1)
ユーザー	kyuridenamida
提出日時	2015-04-26 23:21:42
言語	C++11 (gcc 11.4.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	130 ms 5,376 KB
testcase_03	AC	11 ms 5,376 KB
testcase_04	AC	48 ms 5,376 KB
testcase_05	AC	38 ms 5,376 KB
testcase_06	AC	48 ms 5,376 KB
testcase_07	AC	80 ms 5,376 KB
testcase_08	AC	9 ms 5,376 KB
testcase_09	AC	61 ms 5,376 KB
testcase_10	AC	22 ms 5,376 KB
testcase_11	AC	23 ms 5,376 KB
testcase_12	AC	40 ms 5,376 KB
testcase_13	AC	15 ms 5,376 KB
testcase_14	AC	4 ms 5,376 KB
testcase_15	AC	102 ms 5,376 KB
testcase_16	AC	82 ms 5,376 KB
testcase_17	AC	20 ms 5,376 KB
testcase_18	AC	88 ms 5,376 KB
testcase_19	AC	125 ms 5,376 KB
testcase_20	AC	109 ms 11,092 KB
testcase_21	AC	112 ms 11,008 KB
testcase_22	AC	109 ms 11,008 KB
testcase_23	AC	6 ms 5,376 KB
testcase_24	AC	52 ms 6,784 KB
testcase_25	AC	46 ms 6,528 KB
testcase_26	AC	46 ms 6,272 KB
testcase_27	AC	61 ms 7,552 KB
testcase_28	AC	12 ms 5,376 KB
testcase_29	AC	103 ms 10,368 KB
testcase_30	AC	126 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	35 ms 5,376 KB
testcase_33	AC	53 ms 5,376 KB
testcase_34	AC	42 ms 5,376 KB
testcase_35	AC	34 ms 5,376 KB
testcase_36	AC	94 ms 5,376 KB
testcase_37	AC	8 ms 5,376 KB
testcase_38	AC	110 ms 5,376 KB
testcase_39	AC	40 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
		
	}
	
}

yukicoder

結果

テストケース

ソースコード