题目链接
题意:
如果一个二进制数包含连续的两个1，我们就称这个二进制数是非法的。
小Hi想知道在所有 n 位二进制数（一共有2n个）中，非法二进制数有多少个。
例如对于 n = 3,有 011, 110, 111 三个非法二进制数。
由于结果可能很大，你只需要输出模109+7的余数。
思路:
首先介绍一下官方的题解,缺啥补啥的思想比较6.何为缺啥补啥的,就是我们在用当前的状态去转移的时候,
如果缺少了另一个状态的量,那么我们就补上这个状态的量,转而去求这个状态量,依次类推直到求出为止。
假设f[i]表示i位二进制的非法数目,那么i位二进制肯定可以由i-1位的转化而来了。我们可以想,
当第i位为0时,f[i]=f[i-1]。 即i-1位的二进制数非法,i位才必非法
当第i位为1时,有两种情况:
i-1位是非法的
i-1位是合法的,但是第i-1位是1,这时候我们第i位为1,可以是i位二进制为非法的.
可以很明确的得出当第i位为1时,两种情况互斥.
那么问题又来了,我们怎么求i-1位是合法的且第i-1位是1的呢,这时候采用缺啥补啥的思想,我们记为g[i]。
假设Y是个i位二进制数中末位是1的合法二进制数。那么Y的前i-1位必须是个末位是0的合法二进制数。
我们用h[i]表示末位是0的i位合法二进制数的数目。考虑到h[i]应该是所有i位二进制数的数目(2^i)，减去非法二进制数的数目(f[i])，再减去合法二进制数中末位是1的二进制数(g[i])，所以h[i] = 2^i - f[i] - g[i]。
得到如下方程:
f[i] = f[i-1] * 2 + g[i-1] g[i] = h[i-1] h[i] = 2^i - f[i] - g[i] #include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; ll n; ll f[211],h[211],g[211]; ll quick(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%MOD; a=a*a%MOD; b/=2; } return res%MOD; } int main() { f[1]=0; g[1]=1; h[1]=1; for(int i=2;i<=100;i++) { f[i]=2*f[i-1]+g[i-1]; f[i]%=MOD; g[i]=h[i-1]%MOD; h[i]=quick(2,i)-f[i]-g[i]; h[i]%=MOD; } Rl(n); Pl((f[n]+MOD)%MOD); return 0; }
其实这个题有很多种解法,再说一下我个人的一种解法:
这个题我们对合法的数去递推会更简单可以得到一个斐波那契的转移.
可以想一下,假设f[n]表示n位合法的二进制的个数，那么可以得到f[n]=f[n-1]+f[n-2]。
这是什么意思？也就是代表n位合法的二进制数是由n-1位合法的填0和n-2位合法的填01而来.
其实对于所有的n位二进制数都可以由i-1位的在后面填0或1得来,但是对于第i-1位为1的情况我们还需要特别记录,比较麻烦.我们可以观察到当第i-1位为1,那么第i位为1一定不可以,也就是对于合法的数他的最后两位要么是00 要么是01,要么是10这三种情况.所以当第i位为0时我们直接从i-1位转换而来即可,当第i位为1时,由于前面一位必为0,所以直接在i-2位后填01即可.
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; ll n; ll f[211]; ll quick(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%MOD; a=a*a%MOD; b/=2; } return res%MOD; } int main() { f[1]=2; f[2]=3; for(int i=2;i<=200;i++) { f[i+1]=(f[i-1]+f[i]); f[i+1]%=MOD; } Rl(n); ll ans=quick(2,n)%MOD; ll s=(ans-f[n]%MOD+MOD)%MOD;//需要注意取模后可能会越界...白wa好几发才想起来 Pl(s); return 0; }
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
