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

提出ソース

結果

問題	No.194 フィボナッチ数列の理解(1)
ユーザー	37kt_
提出日時	2016-01-13 18:08:52
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	40 ms / 5,000 ms
コード長	5,840 bytes
コンパイル時間	1,677 ms
コンパイル使用メモリ	173,084 KB
実行使用メモリ	11,488 KB
最終ジャッジ日時	2023-10-19 22:58:52
合計ジャッジ時間	3,478 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,348 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	40 ms 4,348 KB
testcase_03	AC	5 ms 4,348 KB
testcase_04	AC	15 ms 4,348 KB
testcase_05	AC	12 ms 4,348 KB
testcase_06	AC	15 ms 4,348 KB
testcase_07	AC	25 ms 4,348 KB
testcase_08	AC	4 ms 4,348 KB
testcase_09	AC	20 ms 4,348 KB
testcase_10	AC	8 ms 4,348 KB
testcase_11	AC	8 ms 4,348 KB
testcase_12	AC	13 ms 4,348 KB
testcase_13	AC	6 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	31 ms 4,348 KB
testcase_16	AC	27 ms 4,348 KB
testcase_17	AC	7 ms 4,348 KB
testcase_18	AC	28 ms 4,348 KB
testcase_19	AC	39 ms 4,348 KB
testcase_20	AC	3 ms 4,348 KB
testcase_21	AC	25 ms 11,488 KB
testcase_22	AC	1 ms 4,348 KB
testcase_23	AC	4 ms 4,348 KB
testcase_24	AC	13 ms 8,436 KB
testcase_25	AC	12 ms 8,436 KB
testcase_26	AC	12 ms 8,436 KB
testcase_27	AC	13 ms 8,436 KB
testcase_28	AC	6 ms 6,388 KB
testcase_29	AC	22 ms 10,848 KB
testcase_30	AC	40 ms 4,348 KB
testcase_31	AC	2 ms 4,348 KB
testcase_32	AC	12 ms 4,348 KB
testcase_33	AC	18 ms 4,348 KB
testcase_34	AC	14 ms 4,348 KB
testcase_35	AC	12 ms 4,348 KB
testcase_36	AC	30 ms 4,348 KB
testcase_37	AC	4 ms 4,348 KB
testcase_38	AC	33 ms 4,348 KB
testcase_39	AC	13 ms 4,348 KB

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

ソースコード

raw source code

// template {{{
#include <bits/stdc++.h>
using namespace std;

// #define int long long

#define GET_MACRO(a, b, c, d, NAME, ...) NAME
#define REP2(i, n) REP3(i, 0, n)
#define REP3(i, a, b) REP4(i, a, b, 1)
#define REP4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += s)
#define RREP2(i, n) RREP3(i, 0, n)
#define RREP3(i, a, b) for (ll i = (b) - 1; i >= (ll)(a); i--)

#define rep(...) GET_MACRO(__VA_ARGS__, REP4, REP3, REP2)(__VA_ARGS__)
#define rrep(...) GET_MACRO(__VA_ARGS__,, RREP3, RREP2)(__VA_ARGS__)
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define all(c) begin(c), end(c)
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;

template<typename T>
using maxheap = priority_queue<T, vector<T>, less<T>>;

template<typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;

const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const int dx8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

template<typename T>
inline T sq(T x){
	return x * x;
}

template<typename T, typename U>
inline bool chmax(T &x, U y){
	if (x >= y) return false;
	x = y;
	return true;
}

template<typename T, typename U>
inline bool chmin(T &x, U y){
	if (x <= y) return false;
	x = y;
	return true;
}

template<typename T>
inline T& sort(T &c){
	sort(all(c));
	return c;
}

template<typename T>
inline T& reverse(T &c){
	reverse(all(c));
	return c;
}

template<typename T>
inline T& unique(T &c){
	sort(all(c));
	c.erase(unique(all(c)), end(c));
	return c;
}

template<typename T>
inline T sorted(const T &c){
	T d = c;
	return sort(d);
}

template<typename T>
inline T reversed(const T &c){
	T d = c;
	return reverse(d);
}

template<typename T>
inline T uniqued(const T &c){
	T d = c;
	return unique(d);
}

template<typename T>
T power(T x, long long r, const T &e = 1){
	T res(e);
	while (r){
		if (r & 1) res = res * x;
		x = x * x;
		r >>= 1;
	}
	return res;
}
// }}}
// modint {{{
const ll MOD = 1e9 + 7;

struct ModInt {
	ModInt(): v(0){}
	ModInt(ll v): v((v % MOD + MOD) % MOD){}
	ModInt(const std::string &s){
		v = 0;
		for (char c : s){
			v = v * 10 + c - '0';
			if (v >= MOD) v -= MOD;
		}
	}

	operator ll() const {
		return v;
	}

	ModInt operator+(const ModInt &r) const {
		ll res = v + r.v;
		if (res >= MOD) res -= MOD;
		return res;
	}

	ModInt operator-(const ModInt &r) const {
		ll res = v - r.v;
		if (res < 0) res += MOD;
		return res;
	}

	ModInt operator*(const ModInt &r) const {
		return v * r.v % MOD;
	}

	ModInt operator/(const ModInt &r) const {
		return v * r.inv() % MOD;
	}

	ModInt& operator+=(const ModInt &r){
		return *this = *this + r;
	}

	ModInt& operator-=(const ModInt &r){
		return *this = *this - r;
	}

	ModInt& operator*=(const ModInt &r){
		return *this = *this * r;
	}

	ModInt& operator/=(const ModInt &r){
		return *this = *this / r;
	}

	ModInt pow(ll e) const {
		ll res = 1, x = v;
		while (e > 0){
			if (e & 1) res = (res * x) % MOD;
			x = (x * x) % MOD;
			e >>= 1;
		}
		return res;
	}

	ModInt inv() const {
		assert(v != 0);
		return pow(MOD - 2);
	}

private:
	ll v;
};
// }}}
// rig matrix {{{
template<typename T>
class RigMatrix {
public:	
	RigMatrix(): h(0), w(0), z(0), e(1), a(){}
	RigMatrix(int h, int w): h(h), w(w), z(0), e(1), a(h, vector<T>(w, z)){}
	RigMatrix(int h, int w, int z, int e): h(h), w(w), z(z), e(e), a(h, vector<T>(w, z)){}
	
	int height() const { return h; }
	int width() const { return w; }
	
	const T& operator()(int r, int c) const {
		assert(0 <= r && r < h);
		assert(0 <= c && c < w);
		return a[r][c];
	}

	T& operator()(int r, int c){
		assert(0 <= r && r < h);
		assert(0 <= c && c < w);
		return a[r][c];
	}

	RigMatrix operator+(const RigMatrix &r) const {
		assert(h == r.h && w == r.w);
		assert(e == r.e && z == r.z);
		RigMatrix res(h, w, z, e);
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				res[i][j] = (*this)(i, j) + r(i, j);
			}
		}
		return res;
	}

	RigMatrix operator*(const RigMatrix &r) const {
		assert(w == r.h);
		assert(z == r.z && e == r.e);
		RigMatrix res(h, r.w, z, e);
		for (int i = 0; i < h; i++){
			for (int j = 0; j < r.w; j++){
				for (int k = 0; k < w; k++){
					res(i, j) = res(i, j) + (*this)(i, k) * r(k, j);
				}
			}
		}
		return res;
	}

	RigMatrix& operator+=(const RigMatrix &r){
		assert(h == r.h && w == r.h);
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				(*this)(i, j) = (*this)(i, j) + r(i, j);
			}
		}
		return *this;
	}

	RigMatrix& operator*=(const RigMatrix &r){
		return *this = *this * r;
	}
	
private:
	int z, e;
	int h, w;
	vector<vector<T>> a;
};
// }}}

ll n, k;
ll a[1000010];

void solve1()
{
	ModInt s;
	rep(i, n) s += a[i];
	rep(i, n, k){
		a[i] = s;
		s += a[i];
		s -= a[i - n];
	}
	ModInt q;
	rep(i, k) q += a[i];
	cout << a[k - 1] << " " << q << endl;
}

void solve2()
{
	RigMatrix<ModInt> A(n, n);
	RigMatrix<ModInt> B(n, 1);
	RigMatrix<ModInt> E(n, n);
	rep(i, n) A(0, i) = 1;
	rep(i, 1, n) A(i, i - 1) = 1;
	rep(i, n) B(n - i - 1, 0) = a[i];
	rep(i, n) E(i, i) = 1;
	ll p = (power(A, k - 1, E) * B)(n - 1, 0);

	RigMatrix<ModInt> AA(n + 1, n + 1);
	RigMatrix<ModInt> BB(n + 1, 1);
	RigMatrix<ModInt> EE(n + 1, n + 1);
	AA(0, 0) = 2; AA(0, n) = -1;
	rep(i, n) AA(i + 1, i) = 1;
	rep(i, n) BB(n - i, 0) = a[i];
	rep(i, n) BB(0, 0) += a[i];
	rrep(i, n) BB(i, 0) += BB(i + 1, 0);
	rep(i, n + 1) EE(i, i) = 1;
	ll q = (power(AA, k - 1, EE) * BB)(n, 0);

	cout << p << " " << q << endl;
}

int main()
{
	cin >> n >> k;
	rep(i, n) cin >> a[i];
	if (n > 30) solve1();
	else solve2();
}

yukicoder

結果

テストケース

ソースコード