骊山晚照 摄于华清池
题目
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
再加上没有吃蛋糕的20=1种，共有2*（20+21+22）=14种。
假设（!n&1）
//就假设n是6
example2.PNG
再加上没有吃蛋糕的20=1种，共有2*（20+21+22）+2^3=22种。
结合等比数列求和公式
就可以总结出ans和n的关系
就可以写出
O(log n)代码.
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;
}
运行结果
