【t070】二进制

Time Limit: 1 second
Memory Limit: 128 MB

【问题描述】

求所有可以只用1和00拼成的长度为N的二进制数的个数除以15746的余数。
比如当N=4的时候，有5个可能的二进制数：0011，0000，1001，1100，1111。
【数据范围】
1≤N≤1000000
【输入格式】

第一行一个正整数N。
【输出格式】

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

Sample Input

4

Sample Output

5

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t070

【题解】

n=1 1
n=2 11 00
n=3 100 001 111
n=4 1100 0000 0011 1001 1111
即
n=1 1
n=2 2
n=3 3
n=4 5
发现规律f[n] = f[n-1]+f[n-2];
即
在长度为n-2的所有二进制后面再加两个0；
在长度为n-1的所有二进制后面再加1个1；
如11+00=1100 00+00=0000
100+1=1001 001+1=0011 111+1=1111
而这正是n=5的答案；

【完整代码】

#include <cstdio>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
using namespace std;
#define pb push_back;

int main()
{
    //freopen("F:\rush.txt","r",stdin);
    int n;
    scanf("%d",&n);
    if (n==1)
    {
        puts("1");
    }
    else
        if (n==2)
        {
            puts("2");
        }
        else
        {
            int now = 2;
            LL a = 1,b = 2,c;
            while (now < n)
            {
                c = (a+b)%15746;
                a = b;b = c;
                now++;
            }
            printf("%I64d
",c);
        }

    return 0;
}