# HDU 6050 Funny Function （规律+逆元）

## Description

Function $F_{x,y}$ satisfies:

$F_{1,1}=F_{1,2}=1$

$F_{1,i}=F_{1,i-1}+2*F_{1,i-2}\ (i>=3)$

$F_{i,j}=\sum_{k=j}^{j+N-1}F_{i-1,k}\ (i>=2,j>=1)$

For given integers N and M,calculate $F_{m,1}$ modulo 1e9+7.

## Input

There is one integer T in the first line.

The next T lines,each line includes two integers N and M .

1<=T<=10000,1<=N,M<2^63.

## Output

For each given N and M,print the answer in a single line.

## Sample Input

2
2 2
3 3


## Sample Output

2
33


## 思路

// 当 n = 2 时
1 1 3 5 11 21 43 85 171 341
2 4 8 16 32 64 128 256 512 1024
6 12 24 48 96 192 384 768 1536 3072
18 36 72 144 288 576 1152 2304 4608 9216
54 108 216 432 864 1728 3456 6912 13824 27648
162 324 648 1296 2592 5184 10368 20736 41472 82944
486 972 1944 3888 7776 15552 31104 62208 124416 248832
1458 2916 5832 11664 23328 46656 93312 186624 373248 746496
4374 8748 17496 34992 69984 139968 279936 559872 1119744 2239488

// 当 n = 3 时
1 1 3 5 11 21 43 85 171 341
5 9 19 37 75 149 299 597 1195 2389
33 65 131 261 523 1045 2091 4181 8363 16725
229 457 915 1829 3659 7317 14635 29269 58539 117077
1601 3201 6403 12805 25611 51221 102443 204885 409771 819541
11205 22409 44819 89637 179275 358549 717099 1434197 2868395 5736789
78433 156865 313731 627461 1254923 2509845 5019691 10039381 20078763 40157525
549029 1098057 2196115 4392229 8784459 17568917 35137835 70275669 140551339 281102677
3843201 7686401 15372803 30745605 61491211 122982421 245964843 491929685 983859371 1967718741


$2=2^1$

$10=2^1+2^3$

$42=2^1+2^3+2^5$

$170=2^1+2^3+2^5+2^7$

$F_{3,1}=F_{2,1}×(2^n-1)-cha$

$F_{4,1}=F_{3,1}×(2^n-1)-cha=F_{2,1}×(2^n-1)^2-cha×(2^n-1)-cha$

$F_{5,1}=F_{4,1}×(2^n-1)-cha=F_{2,1}×(2^n-1)^3-cha×(2^n-1)^2-cha×(2^n-1)-cha$

$F_{m,1}=F_{m-1,1}×(2^n-1)-cha=F_{2,1}×(2^n-1)^{m-2}-cha×(2^n-1)^{m-3}…-cha$

S[i]: 1 2 5 10 21 42 85 170 341 682 1365 2730 5461 10922 21845 43690 87381 174762 349525
F[i]: 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763 349525


$S_i$ 代表 $F_{1,i}$ 的前 $i$ 项和，将 $S$ 统一右移一个会发现什么呢？

## AC 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include<iostream>
using namespace std;

typedef __int64 LL;
const int mod = 1e9+7;
LL n,m;
LL mult(LL a,LL n)
{
LL ans=1;
while(n)
{
if(n&1)ans=(ans*a)%mod;
a=(a*a)%mod;
n>>=1;
}
return ans;
}

void solve()
{
if(m==1)
{
cout<<"1"<<endl;
return;
}
LL three=mult(3,mod-2);         // 3 的逆元
LL one=((mult(2,n+1)+(n&1?-1:1)+mod)%mod*three)%mod;    // F[1][n+1]
if(n%2==0)one=(one-1+mod)%mod;  // 计算 F[2][1]
LL ans=0;
LL mu=(mult(2,n)-1+mod)%mod;    // 2^n-1
LL mun=mult(mu,m-2);            // (2^n-1)^(m-2)
if(n%2==0)                      // 偶数时
ans=(one*mun)%mod;
else                            // 奇数时
{
LL cha=n/2;
cha=((2*(mult(4,cha)-1+mod)%mod)%mod)*three%mod;
}
cout<<ans<<endl;
}

int main()
{
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
solve();
}
return 0;
}


### 6 只已被捕捉

• 温姑娘 Edge | 15.15063 Windows 10

能不能转载你的博客？写的太清晰了。

• 千千 Chrome | 60.0.3107.4 Windows 10

可以呀~ （也可以偷偷的加上链接

• 伴梦人 Chrome | 59.0.3071.115 Windows 10

比官方好理解n多倍，感谢分享。（ps：博客很漂亮！）

• 千千 Chrome | 60.0.3107.4 Windows 10

嗯呢，谢谢支持，官方的题解好简单，难道是我想复杂了，可能写的复杂点是因为我忘记了数学归纳法，总之就这样啦~