hiho一下 第158周 非法二进制数 （dp）

hiho一下 第158周 非法二进制数 （dp）

描述

如果一个二进制数包含连续的两个1，我们就称这个二进制数是非法的。小Hi想知道在所有 n 位二进制数（一共有2n个）中，非法二进制数有多少个。例如对于 n = 3,有 011, 110, 111 三个非法二进制数。由于结果可能很大，你只需要输出模109+7的余数。

输入

一个整数 n (1 ≤ n ≤ 100)。

输出

n 位非法二进制数的数目模10^9+7的余数。

样例输入

3

样例输出

3

思路

令 ​​dp[i][x]​​​ 代表长度为 ​​i​​​ ，末尾为 ​​x​​ 的合法二进制数的个数，于是非法二进制数个数便是 2n−dp[n][0]−dp[n][1]

对于每一个合法二进制数来说，它的末尾有两种情况： ​​0​​​ 或 ​​1​​ 。

末尾为 ​​0​​ 时可以由前一个状态末尾任意转移而来。

末尾为 ​​1​​​ 时只能由前一个状态末尾为 ​​0​​ 转移。

于是便有：

dp[i][0]=dp[i−1][0]+dp[i−1][1]

dp[i][1]=dp[i−1][0]

AC 代码

#include using namespace std;typedef long long LL;const int mod = 1e9+7;LL dp[105][2];void init(){ dp[1][0]=dp[1][1]=1; for(int i=2; i<=100; i++) { dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod; dp[i][1]=dp[i-1][0]; }}int main(){ init(); int n; while(cin>>n) { int cnt = (dp[n][0]+dp[n][1])%mod; int ans=1; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。