简答题
偏难
#13168
选数 题目描述 给定一个正整数 n,从数字 1 到 n 中选择若干个数字(所选集合不能为空),且任意两个被选中的数字在数轴上不能相邻。求符合条件的方案数,结果对…
选数
题目描述
给定一个正整数 n,从数字 1 到 n 中选择若干个数字(所选集合不能为空),且任意两个被选中的数字在数轴上不能相邻。求符合条件的方案数,结果对 1000000007 取模。
输入格式
第一行:单个整数 n。
输出格式
输出一个整数,表示方案数模 1000000007 的结果。
输入样例
3
输出样例
4
说明提示
· 对于 30% 的数据,n≤20;
· 对于 60% 的数据,n≤10,000;
· 对于 100% 的数据,1≤n≤100,000。
限制
时间限制:1000ms
内存限制:512MiB
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int main() {
int n;
cin >> n;
if (n == 1) {
cout << 1 << endl;
return 0;
}
vector<long long> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i) {
dp[i] = (dp[i-1] + dp[i-2] + 1) % MOD;
}
cout << dp[n] << endl;
return 0;
}</pre>
这道题暂未补解析。