Problem
有多少个长度为n的二进制串,即不存在3个连续的1,也不存在3个连续的0。
例如n = 4,共有16个长度为4的01串,其中0000 0001 1000 1111 0111 1110,不符合要求,所以共有10个符合要求的串。
Solution
2657 二进制数字-题解
推荐买题解,这题解tql。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include<iostream> #include<stdio.h> #include<algorithm> #include<map> #include<queue> #include<cstring> #include<stack> #define mem(ss) memset(ss,0,sizeof(ss)) typedef long long ll; typedef long double ld; typedef __int128 lll; const ll mod=1e9+7; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;} int n; ll a[5]={0,2,4}; int main(){ io_opt; cin>>n; if(n<=2){ cout<<a[n]<<endl; return 0; } ll d1=2,d2=4,cur; for(int i=3;i<=n;i++){ cur=(d1+d2)%mod; d1=d2%mod; d2=cur; } cout<<cur<<endl;
return 0; }
|