评测记录 这道题，我采取了小数据用暴力，大数据用正解的思路，但是不知道为什么只有88pts.样例都过了.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 3;
const int mod = 100000000;
typedef long long ll;
ll f[16298655];
struct matrix {
	ll m[maxn][maxn];
	matrix() {memset(m, 0, sizeof(m));}
};
matrix operator * (const matrix& a, const matrix& b) {
	matrix c;
	memset(c.m, 0, sizeof(c.m));
	for (int i = 1; i <= 2; i++) {
		for (int j = 1; j <= 2; j++) {
			for (int k = 1; k <= 2; k++) {
				c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
			}
		}
	}
	return c;
}
inline ll read() {
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x * 10 + ch - 48) % 150000000; ch = getchar();}
	return x * f;
}
matrix base, res;
void init() {
	base.m[1][1] = base.m[1][2] = base.m[2][1] = 1;
	base.m[2][2] = 0;
	res.m[1][1] = 2; res.m[2][1] = 3;
}
matrix qpow(matrix a, ll p) {
	while (p) {
		if (p & 1) {
			res = res * a;
		}
		a = a * a;
		p >>= 1;
	}
	return res;
}
ll n;
void init2() {
    f[1] = 1, f[2] = 2, f[3] = 3;
    for (int i = 4; i <= 16298651; i++) {
        f[i] = (f[i - 1] % mod + f[i - 2] % mod) % mod;
    }
}
int main() {
	n = read();
	if (n <= 16298650) {
	    init2();
	    printf("%lld\n", f[n] % mod);
	    return 0;
	}
	if (n <= 3) {
		printf("%lld\n", n);
		return 0;
	}
	init();
	matrix t = qpow(base, n);
	printf("%lld\n", t.m[1][1] / 2 % mod);
	return 0;
}