17暑假多校联赛2.6 HDU 6050 Funny Function

Funny Function

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
?

Problem Description

Function Fx,ysatisfies:

For given integers N and M,calculate Fm,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

?
题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=6050
?

分析

题意：给定一组关系式，然后给出关系式中的N，再给定一个M，求Fm,1
打表找规律题，可以自己用Excel快速打一份表，推一推

n=2 1 1 3 5 11 21 2 4 8 16 32 64 6 12 24 48 96 192 18 36 72 144 288 576 54 108 216 432 864 1728 162 324 648 1296 2592 5184

n=3 1 1 3 5 11 21 5 9 19 37 75 149 33 65 131 261 523 1045 229 457 915 1829 3659 7317 1601 3201 6403 12805 25611 51221 11205 22409 44819 89637 179275 358549

n=4 1 1 3 5 11 21 10 20 40 80 160 320 150 300 600 1200 2400 4800 2250 4500 9000 18000 36000 72000 33750 67500 135000 270000 540000 1080000 506250 1012500 2025000 4050000 8100000 16200000

n=5 1 1 3 5 11 21 21 41 83 165 331 661 641 1281 2563 5125 10251 20501 19861 39721 79443 158885 317771 635541 615681 1231361 2462723 4925445 9850891 19701781 19086101 38172201 76344403 152688805 305377611 610755221 

推的比较乱也就不写出来了，可以对照表格自己推一推
直接拿出大佬们推出的公式
F(m,1)=( 2 * k ^ (m - 1)+(1+ (-1) ^ (n + 1)) / 2) / 3 , k = (2 ^ n -1);
这道题目中还要用以下两种算法：
?

整数快速幂

?
详解点击标题查看
?

逆元详解

当题目中数据较大，而且计算中出现过除法的时候，往往取模会出错，所以要用到逆元
若， b*b1%c≡1
则，b1称为b模c的乘法逆元
在ACM中，许多除法取模都要用到求逆元
(a/b)%c≡(a*b1)%c
?
详解点击标题查看
?

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=1e5 + 10;
const int mod=1e9 + 7;
typedef long long LL;
LL km(LL a,LL b)///整数快速幂
{LL ans=1;while(b){if(b&1)ans=(ans*a)%mod;b>>=1;a=(a*a)%mod;}return ans;
}
int main()
{int T;scanf("%d",&T);while(T--){LL n,m;scanf("%lld %lld",&n,&m);LL k=(km(2,n)-1+mod)%mod;LL k1=(km(k,m-1)*2)%mod;LL k2=(1+km(-1,n+1))*km(2,mod-2);printf("%lld\n",((k1+k2)%mod*km(3,mod-2))%mod);}return 0;
}