打卡信奥刷题（2859）用C++实现信奥题 P4910 帕秋莉的手环

P4910 帕秋莉的手环

题目背景

帕秋莉是蕾米莉亚很早结识的朋友，现在住在红魔馆地下的大图书馆里。不仅擅长许多魔法，还每天都会开发出新的魔法。只是身体比较弱，因为哮喘，会在咏唱符卡时遇到麻烦。

她所用的属性魔法，主要是生命和觉醒的“木”，变化和活动的“火”，基础和不动的“土”，果实和丰收的“金”，寂静和净化的“水”，机动和攻击的“日”，被动和防御的“月”七种属性

没有窗户的图书馆或许充满了灰尘，不过她认为在书旁边才是自己，所以她不能从书的旁边离开。这样已经一百年了。

题目描述

经过数年魔法的沉淀，帕秋莉将她那浩瀚无边的魔法的一部分浓缩到了一些特质的珠子中。

由于帕秋莉爱好和平，她只把象征生命和觉醒的木属性魔法和果实和丰收的金属性魔法放入了珠子中。

她认为光要这些珠子没有什么用处，于是她想将这些珠子串成魔法手环，这样就好看多了。于是，她拿出来用来串这些珠子的线 – 雾雨灵径。

她将这些珠子串到一起之后发现了一些性质：只要相邻珠子间的两个珠子中有一个是金属性的，那么它们之间的雾雨灵径的颜色就为金色。

帕秋莉想要一个全都是金色的手环，而且她还想知道一共有多少种方案。由于她还要研究新的魔法，她就把这件事交给了你。由于她的魔法浩瀚无边，她有无穷的珠子。

她并不想看着好几十位的数字，于是你需要对 $1000000007$ 进行取模。

输入格式

输入包含多组数据。

第一行一个正整数 $T$ ，表示数据组数。

之后每组数据有一个 $n$ 代表木属性珠子和金属性珠子的总个数。

输出格式

对于每组数据，输出取模后的方案数。

输入输出样例 #1

输入 #1

2
5
20

输出 #1

11
15127

输入输出样例 #2

输入 #2

3
9
99
999

输出 #2

76
281781445
445494875

输入输出样例 #3

输入 #3

5
123
1234
12345
123456
1234567

输出 #3

528790589
200102666
537707871
262341000
534036342

说明/提示

这里给出 $n=5$ 时，样例的解释：

使用 $1,2,3,4,5$ 来代表各个珠子。

可行的方案是（其中的数字代表染成金元素的珠子序号）：

$\{1,3,5\},\{1,2,4\},\{1,3,4\},\{2,3,5\},\{2,4,5\}$

$\{1,2,3,4\},\{1,2,3,5\},\{1,2,4,5\},\{1,3,4,5\},\{2,3,4,5\}$

$\{1,2,3,4,5\}$

对于 $20\%$ 的数据，有 $1\le n\le 10$ ；

对于 $40\%$ 的数据，有 $1\le n\le 10^2$ ；

对于 $60\%$ 的数据，有 $1\le n\le 10^6$ ；

对于 $90\%$ 的数据，有 $1\le n\le 10^9$ ；

对于全部的数据，有 $1\le T\le 10,1\le n\le 10^{18}$。

C++实现

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, dp[N][2];
void calc()
{
for (int i = 2; i <= n; i++)
dp[i][0] = dp[i – 1][1],
dp[i][1] = (dp[i – 1][0] + dp[i – 1][1]) % mod;
}
void solve()
{
long long ans = 0;
scanf("%d", &n);

dp[1][0] = 1, dp[1][1] = 0;
calc(), ans = (ans + dp[n][1]) % mod;

dp[1][0] = 0, dp[1][1] = 1;
calc(), ans = (ans + dp[n][0] + dp[n][1]) % mod;

cout << ans << '\\n';
}
int main()
{
ios::sync_with_stdio(false);
int T;
scanf("%d", &T);
while (T—) solve();
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容