题目背景
帕秋莉是蕾米莉亚很早结识的朋友，现在住在红魔馆地下的大图书馆里。不仅擅长许多魔法，还每天都会开发出新的魔法。只是身体比较弱，因为哮喘，会在咏唱符卡时遇到麻烦。
她所用的属性魔法，主要是生命和觉醒的“木”，变化和活动的“火”，基础和不动的“土”，果实和丰收的“金”，寂静和净化的“水”，机动和攻击的“日”，被动和防御的“月”七种属性
没有窗户的图书馆或许充满了灰尘，不过她认为在书旁边才是自己，所以她不能从书的旁边离开。这样已经一百年了。
题目描述
经过数年魔法的沉淀，帕秋莉将她那浩瀚无边的魔法的一部分浓缩到了一些特质的珠子中。
由于帕秋莉爱好和平，她只把象征生命和觉醒的木属性魔法和果实和丰收的金属性魔法放入了珠子中。
她认为光要这些珠子没有什么用处，于是她想将这些珠子串成魔法手环，这样就好看多了。于是，她拿出来用来串这些珠子的线 - 雾雨灵径。
她将这些珠子串到一起之后发现了一些性质：只要相邻珠子间的两个珠子中有一个是金属性的，那么它们之间的雾雨灵径的颜色就为金色。
帕秋莉想要一个全都是金色的手环，而且她还想知道一共有多少种方案。由于她还要研究新的魔法，她就把这件事交给了你。由于她的魔法浩瀚无边，她有无穷的珠子。
她并不想看着好几十位的数字，于是你需要对 1000000007 进行取模。
输入格式
输入包含多组数据。
第一行一个正整数 T ，表示数据组数。
之后每组数据有一个 n 代表木属性珠子和金属性珠子的总个数。
输出格式
对于每组数据，输出取模后的方案数。
输入输出样例
输入 #1复制
2 5 20
输出 #1复制
11 15127
输入 #2复制
3 9 99 999
输出 #2复制
76 281781445 445494875
输入 #3复制
5 123 1234 12345 123456 1234567
输出 #3复制
528790589 200102666 537707871 262341000 534036342
说明/提示
这里给出 n=5 时，样例的解释：
使用 1,2,3,4,5 来代表各个珠子。
可行的方案是（其中的数字代表染成金元素的珠子序号）：
{1,3,5},{1,2,4},{1,3,4},{2,3,5},{2,4,5}
{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}
{1,2,3,4,5}
对于 20% 的数据，有 1≤n≤10 ；
对于 40% 的数据，有 1≤n≤102 ；
对于 60% 的数据，有 1≤n≤106 ；
对于 90% 的数据，有 1≤n≤109 ；
对于全部的数据，有 1≤T≤10,1≤n≤1018。
代码实现：
#include<iostream> #include<cstdio> #include<cstdlib> #include<map> #define LL long long #define re register #define res mp[l][r][len] using namespace std; const int mod=1000000007; int T; LL n, f[70][2][2], pow2[70]; map<LL,LL> mp[2][2]; LL dfs(LL len, int l, int r, int x){ if(mp[l][r][len]) return mp[l][r][len]; for(re int i=x;~i;--i){ if(pow2[i]==len) return f[i][l][r]; if(pow2[i]<len){ LL a=dfs(len-pow2[i],0,r,i-1), b=dfs(len-pow2[i],1,r,i-1); res=(res+(f[i][l][0]*b)%mod)%mod; res=(res+(f[i][l][1]*a)%mod)%mod; res=(res+(f[i][l][1]*b)%mod)%mod; return res; } } return 0; } int main(){ scanf("%d",&T); f[0][0][0]=f[0][1][1]=pow2[0]=1ll; for(re int i=1;i<=62;++i){ pow2[i]=pow2[i-1]*2; for(re int j=0;j<=1;++j){ for(re int k=0;k<=1;++k){ f[i][j][k]=(f[i][j][k]+(f[i-1][j][0]*f[i-1][1][k])%mod)%mod; f[i][j][k]=(f[i][j][k]+(f[i-1][j][1]*f[i-1][0][k])%mod)%mod; f[i][j][k]=(f[i][j][k]+(f[i-1][j][1]*f[i-1][1][k])%mod)%mod; } } } for(re int i=1;i<=T;++i){ scanf("%lld",&n); printf("%lld\n",(dfs(n+1,0,0,62)+dfs(n+1,1,1,62))%mod); } return 0; }
