【个人学习记录】快速幂算法/位运算 [ZCMU OJ]1202: 3的幂的和1417: 2048

本文主要是介绍【个人学习记录】快速幂算法/位运算 [ZCMU OJ]1202: 3的幂的和1417: 2048，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

求：3^0 + 3^1 +...+ 3^(N) mod 1000000007。

Input

每行一个整数N(0 <= N <= 10^9)

Output

输出：计算结果

Sample Input

Sample Output

HINT

(a/b)%c=(a%(b*c))/b (a 能整除b)

---------------------------------------------------------------------------------------------------------------------------------

写点废话：今天看《数据结构与算法分析》p26-27，其中提到幂运算。刚好想到了快速幂算法（虽然我听说过这个算法但当时并不会），结果我以为书上的取幂运算就是针对这道题的最优算法，想现学现用一下。结果发现要么tle要么wa，折腾了好久。。。最最开始遇到这个题目用的for循环（当然这肯定超时了）。。既然要解决这道题那么就要涉及到数据结构，我就上网学习了一波快速幂算法。

---------------------------------------------------------------------------------------------------------------------------------

书上的取幂运算计算X^N运用到了递归思想，指数为0则结果返回1，指数为1则返回X本身。如果指数是偶数，则将X^N变为X^(N/2)*X^(N/2)；是奇数则将X^N变为X^(N/2)*X^(N/2)*X；所需要的乘法次数最多是2logN。

long int Pow(long int X,unsigned int N)
{if(N==0)return 1;else if(N==1)return X;if(N%2==0)return Pow(X*X,N/2);elsereturn Pow(X*X,N/2)*X;
}

按照相同的思路以及我通过学习之后的理解，我把最初用for暴力循环替换成了如下代码（其中maxn=1e9+7）；底数平方，指数减半；若指数为奇数则减去1使指数为偶数再除以2。

long long qp(long long base,long long power)
{long long result=1;while(power>0){if(power%2==0){base=(base*base)%maxn;power/=2;	}else{power--;result=(result*base)%maxn;power/=2;base=(base*base)%maxn;}}return result;
}

假设计算x^43，程序如下运行：

尽管如此，程序依然超时了。那么可以利用位运算替换一些语句。

power%2==1 可替换为 power&1 （与运算）

power/=2 可替换为 power>>=1（将power的二进制位向右移动一位则可使power变为原来的一半）

再次优化，其中求和利用等比数列求和公式 Sn = ( a1*(1-q^n) )/(1-q) 即可。a1=1,q=3;

注意：除以一个数mod另一个数等于乘以这个数的逆元。

学习并掌握核心思路再把思路翻译为代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e9+7;
long long qp(long long power)
{long long result=1,base=3;while(power>0){if(power&1){result=(base*result)%maxn;}power>>=1;base=(base*base)%maxn;}return result;
}
int main()
{long long n;while(cin>>n){cout<<(qp(n+1)-1)*(500000004)%maxn<<endl;}
}

注意：对于取余运算，(a/b)%c != (a%c / b%c) %c;

(a/b)%c=(a%(b*c))/b (a 能整除b)

---------------------------------------------------------------------------------------------------------------------------------

Description

想必大家都玩过2048的游戏，小明想知道这个游戏能出现的最高数字是多少？请你帮忙计算，当然小明玩的2048和我们的不太一样，小明的2048不一定是4X4的格子，可以使3X2等等。小明的2048只能随机生成2。

Input

输入n，m(0<=n,m<=10^4)表示有2048游戏矩阵的大小，当0，0时结束；

Output

输出理论最大值,答案对1000000007取余。

Sample Input

2 2 0 0

Sample Output

---------------------------------------------------------------------------------------------------------------------------------

思路同理，注意m或n等于0的情况，上ac代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e9+7;
long long QuickPower(long long base,long long power)
{long long result=1;while(power>0){if(power&1){result=result*base%maxn;}power>>=1;base=(base*base)%maxn;}return result;
}
int main()
{long long n,m;while(~scanf("%lld %lld",&n,&m)&&(n!=0||m!=0)){if(n==0||m==0)cout<<"0"<<endl;elsecout<<QuickPower(2,(m*n)%maxn)<<endl;}
}

这篇关于【个人学习记录】快速幂算法/位运算 [ZCMU OJ]1202: 3的幂的和1417: 2048的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！