骊山晚照 摄于华清池

题目

http://www.tyvj.cn/p/1991

N 只小猫来到了Freda 的城堡做客！Freda 很高兴，拿出了蛋糕和饼干来招待它们，每一只小猫都可以吃到蛋糕或者饼干，当然，每只小猫具体拿到的是蛋糕还是饼干是由Freda 决定的。

小猫们看到蛋糕比饼干大之后，普遍认为蛋糕比饼干要好>.<。所以，如果Freda 给了第i 只小猫蛋糕且这个小猫是第一个吃到蛋糕的，那么就必须给第i+2,i+4,i+6......只小猫蛋糕。

也就是说，如果存在正整数i,满足：

1、对于所有的0<j<i,第j 只小猫吃到的是饼干

2、第i 只小猫吃到的是蛋糕

那么就必须有：对于所有的i<k<=N, k mod 2 = i mod 2,第k 只小猫吃到的是蛋糕。小猫的数目一多，Freda 就忙不过来了。请你帮忙计算，Freda 一共有多少种可能的方法来招待这N 只小猫？

输入

一个整数n，表示小猫个数

输出

输出一个整数，表示freda招待这N 只小猫的方法数。由于这个数可能很大，你只需要输出它mod 1000000007 的值。

解释

大致思路:等比数列+快速幂

经分析，不难得知，当第一个吃蛋糕的小猫确定时，之后所有小猫中必须吃蛋糕的猫随之确定。

如：共有7个猫，假设第一个吃蛋糕的是第二个,那么形成情况如下：BD _ D_D_ .

则情况“共有7个猫，假设第一个吃蛋糕的是第二个”的方法数等于二的（空白下划线个数）次方。

那么这个问题 可以 转化成公比是2的等比数列求和问题：

假设n&1（n是奇数）

//就假设n是5

example1.PNG

再加上没有吃蛋糕的2^{0=1种，共有2*（2}0+2¹⁺²2）=14种。

假设（!n&1）

//就假设n是6

example2.PNG

结合等比数列求和公式

C++代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int maxn=100000+10;
const int mod=1000000007;
inline ll POW(ll a,ll b) {
    ll ans=1,base=a;
    while(b!=0) {
        if(b&1!=0)
            ans=ans*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ans%mod;
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    if(n&1){
        n=n/2+1;
        cout<<2*((1-POW(2,n))/(1-2))%mod;
    }
    else{
        int N=n/2-1+1;
        cout<<(2*((1-POW(2,N))/(1-2))+POW(2,n/2))%mod;
    }
    return 0;
}

运行结果