【JZOJ1304】Binary

　

binary

description

求所有可以只用1和00拼成的长度为N的二进制数的个数除以15746的余数。

比如当N=4的时候，有5个可能的二进制：0011，0000，1001，1100，1111。

---

analysis

• 长度为$n$n的串只能由长$n-1$n−1的串拼接$1$1，或长$n-2$n−2的串拼接$00$00得到

• 即$f\left[n\right]=f[n-1]+f[n-2]$f[n]=f[n−1]+f[n−2]，暴力斐波那契数列

---

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 1000005
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
#define O3 __attribute__((optimize("-O3")))

using namespace std;

ll f[MAXN];
ll n;

O3 inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
O3 int main()
{
	n=read(),f[0]=f[1]=1;
	fo(i,2,n)f[i]=(f[i-1]+f[i-2])%15746;
	printf("%lld\n",f[n]);
	return 0;
}

相关阅读