題目
N 只小貓來到了Freda 的城堡做客！Freda 很高興嘿期，拿出了蛋糕和餅干來招待它們盲镶，每一只小貓都可以吃到蛋糕或者餅干，當(dāng)然骇窍，每只小貓具體拿到的是蛋糕還是餅干是由Freda 決定的镐确。
小貓們看到蛋糕比餅干大之后包吝，普遍認(rèn)為蛋糕比餅干要好>.<饼煞。所以，如果Freda 給了第i 只小貓蛋糕且這個(gè)小貓是第一個(gè)吃到蛋糕的诗越，那么就必須給第i+2,i+4,i+6......只小貓蛋糕砖瞧。
也就是說，如果存在正整數(shù)i,滿足：
1掺喻、對(duì)于所有的0<j<i,第j 只小貓吃到的是餅干
2芭届、第i 只小貓吃到的是蛋糕
那么就必須有：對(duì)于所有的i<k<=N, k mod 2 = i mod 2,第k 只小貓吃到的是蛋糕储矩。小貓的數(shù)目一多感耙，F(xiàn)reda 就忙不過來了。請(qǐng)你幫忙計(jì)算持隧，F(xiàn)reda 一共有多少種可能的方法來招待這N 只小貓即硼？
輸入
一個(gè)整數(shù)n，表示小貓個(gè)數(shù)
輸出
輸出一個(gè)整數(shù)屡拨，表示freda招待這N 只小貓的方法數(shù)只酥。由于這個(gè)數(shù)可能很大，你只需要輸出它mod 1000000007 的值呀狼。
解釋
大致思路:等比數(shù)列+快速冪
經(jīng)分析裂允，不難得知，當(dāng)?shù)谝粋€(gè)吃蛋糕的小貓確定時(shí)哥艇，之后所有小貓中必須吃蛋糕的貓隨之確定绝编。
如：共有7個(gè)貓，假設(shè)第一個(gè)吃蛋糕的是第二個(gè),那么形成情況如下：BD _ D_D_ .
則情況“共有7個(gè)貓貌踏，假設(shè)第一個(gè)吃蛋糕的是第二個(gè)”的方法數(shù)等于二的（空白下劃線個(gè)數(shù)）次方十饥。
那么這個(gè)問題 可以 轉(zhuǎn)化成公比是2的等比數(shù)列求和問題：
假設(shè)n&1（n是奇數(shù)）
//就假設(shè)n是5
再加上沒有吃蛋糕的20=1種，共有2*（20+21+22）=14種祖乳。
假設(shè)（!n&1）
//就假設(shè)n是6
再加上沒有吃蛋糕的20=1種逗堵，共有2*（20+21+22）+2^3=22種。
結(jié)合等比數(shù)列求和公式
就可以總結(jié)出ans和n的關(guā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;
}
運(yùn)行結(jié)果
