题目背景帕秋莉是蕾米莉亚很早结识的朋友现在住在红魔馆地下的大图书馆里。不仅擅长许多魔法还每天都会开发出新的魔法。只是身体比较弱因为哮喘会在咏唱符卡时遇到麻烦。她所用的属性魔法主要是生命和觉醒的“木”变化和活动的“火”基础和不动的“土”果实和丰收的“金”寂静和净化的“水”机动和攻击的“日”被动和防御的“月”七种属性没有窗户的图书馆或许充满了灰尘不过她认为在书旁边才是自己所以她不能从书的旁边离开。这样已经一百年了。题目描述经过数年魔法的沉淀帕秋莉将她那浩瀚无边的魔法的一部分浓缩到了一些特质的珠子中。由于帕秋莉爱好和平她只把象征生命和觉醒的木属性魔法和果实和丰收的金属性魔法放入了珠子中。她认为光要这些珠子没有什么用处于是她想将这些珠子串成魔法手环这样就好看多了。于是她拿出来用来串这些珠子的线 - 雾雨灵径。她将这些珠子串到一起之后发现了一些性质只要相邻珠子间的两个珠子中有一个是金属性的那么它们之间的雾雨灵径的颜色就为金色。帕秋莉想要一个全都是金色的手环而且她还想知道一共有多少种方案。由于她还要研究新的魔法她就把这件事交给了你。由于她的魔法浩瀚无边她有无穷的珠子。她并不想看着好几十位的数字于是你需要对 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说明/提示这里给出 n5 时样例的解释使用 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。代码实现#includeiostream #includecstdio #includecstdlib #includemap #define LL long long #define re register #define res mp[l][r][len] using namespace std; const int mod1000000007; int T; LL n, f[70][2][2], pow2[70]; mapLL,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 ix;~i;--i){ if(pow2[i]len) return f[i][l][r]; if(pow2[i]len){ LL adfs(len-pow2[i],0,r,i-1), bdfs(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 i1;i62;i){ pow2[i]pow2[i-1]*2; for(re int j0;j1;j){ for(re int k0;k1;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 i1;iT;i){ scanf(%lld,n); printf(%lld\n,(dfs(n1,0,0,62)dfs(n1,1,1,62))%mod); } return 0; }