[洛谷P4910]帕秋莉的手环

题目大意：有一个$n(n\leqslant10^{18})$个点的环，每个点可以是$0$或$1$，要求相邻点中至少一个$1$，问方案数，多组询问。

题解：先考虑是一条链的情况，令$f_{i,j}$表示到了第$i$个点，这个点是$j$的方案数。
$$
f_{i+1,0}=f_{i,1}\\
f_{i+1,1}=f_{i,0}+f_{i,1}
$$
再考虑一个环的情况，当第一点为$0$时，最后一个点只能选$1$，否则都可以。然后发现是$F_{n-1}+F_{n+1}$（$F_n$表示斐波那契数列第$n$项）

卡点：传值时把$long\;long$传成$int$

C++ Code：

#include <cstdio>

const int mod = 1e9 + 7;

inline int getreduce(int x) { return x + (x >> 31 & mod); }

struct Matrix {

	int s[2][2];

	inline Matrix operator * (const Matrix &rhs) {

		Matrix res;

		for (int i = 0; i < 2; ++i)

			for (int j = 0; j < 2; ++j) {

				long long t = 0;

				for (int k = 0; k < 2; ++k) t += static_cast<long long> (s[i][k]) * rhs.s[k][j];

				res.s[i][j] = t % mod;

			}

		return res;

	}

} base, res;

inline int calc(long long n) {

	if (!n) return 0;

	if (n == 1) return 1;

	res.s[0][0] = res.s[0][1] = 1;

	base.s[0][0] = base.s[0][1] = base.s[1][0] = 1, base.s[1][1] = 0;

	for (n -= 2; n; n >>= 1, base = base * base) if (n & 1) res = res * base;

	return **res.s;

}

int Tim;

long long n;

int main() {

	scanf("%d", &Tim);

	while (Tim --> 0) {

		scanf("%lld", &n);

		printf("%d\n", getreduce(calc(n - 1) + calc(n + 1) - mod));

	}

	return 0;

}

巴特西

[洛谷P4910]帕秋莉的手环

最新文章

热门文章