首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int MOD = 1000000007; int main() {     int n;     cin &gt;&gt; n;     if (n == 1) {         cout &lt;&lt; 1 &lt;&lt; endl;         return 0;     }     vector&lt;long long&gt; dp(n + 1);     dp[1] = 1;     dp[2] = 2;     for (int i = 3; i &lt;= n; ++i) {         dp[i] = (dp[i-1] + dp[i-2] + 1) % MOD;     }     cout &lt;&lt; dp[n] &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。