22.7暑假冲刺联训CSP-J 第二场II
第二题人行横道
题目描述
一条有 n 条线的人行横道，这 n 条线是交错的，即一条黑线一条白线。
Noder 要过马路，他不能一步完全跨过马路，途中至少要有一次踩在一条线上。他希望自己每走一步踩过的线，也是黑白交替的 单独一条白线或黑线，也算黑白交替 ，问他有多少种不同的走法。
由于数量太多，只需要输出对 1e9+7 取模的结果。
输入
第一行包含一个整数n（1 ≤ n ≤ 10^6），对应人行横道的长度。
输出
输出可行的方案数对 1e9+7 取模的结果。
数据范围
对于40%的数据，1≤n≤20；
对于60%的数据，1≤n≤1000；
对于100%的数据，1≤n≤106；
输入样例
3
输出样例
6
样例解释
设 3 条线编号为 1,2,3 ，符合条件的走法包括：（以下方案中的数字表示踩到的线）
1 1,2,3
2 1,2
3 2,3
4 1
5 2
6 3
动态规划不知怎么写。
#include <bits/stdc++.h>
using namespace std;
long long f[1000005],n,m=1e9+7,s;
int main()
{
cin>>n;
f[1]=1;
for(long long i=2;i<=n;i++)
{
s=-s;
s-=f[i-2];
f[i]=f[i-1]+f[i-1]+m+s+1;
f[i]%=m;
s%=m;
}
cout<<f[n];
return 0;
}