[洛谷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 
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 (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;
}

转载于:https://www.cnblogs.com/Memory-of-winter/p/10354819.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！